백준 [1929번] :: 소수구하기 (Python , 파이썬)

www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

에라토스테네스의 체를 이용하라는 문제이다.

 

 처음 쓴 코드:

 

 

M,N = map(int,input().split())
oup = []
for i in range(M,N+1):

    
    if i == 2:
        oup.append(i)

    else:
        for j in range(2,i):
            if i % j == 0:
                break
            elif j == i - 1:
             oup.append(i)

for i in oup:
    print(i)


    

 

위 코드는 M부터 N까지 숫자를,  자기 자신과 1을 제외하고 모두 검사를 하여 소수를 출력하였다.  이렇게 하면 문제는 풀렸지만 시간초과가 떳다. 생각을 해보니 모두 검사할 필요가 없다는 것을 느끼긴 했지만, 어떻게 범위를 지정해야 할 지 몰라서 인터넷에 검색을 해보았다. 첫번째로는 함수를 정의하여 풀었고, 두번째로는 범위를 해당 숫자보다 -1까지 검사하는 것이 아니라 제곱근까지 검사를 하면 소수를 확인 할 수 있다는것을 알았다. 

 

파이썬에서는 제곱근을 구하는 방법으로는 

1. math.sqrt을 사용한다.

2. 임의의 숫자Num에 ** 0.5 을 사용한다.

 

 

 

 결과 코드: 

 

 

import math

def Dis(num):
   
   if num == 1: return False

   a = int(math.sqrt(num))
   
   for i in range(2, a+1):
      if num % i == 0: return False
      return True

m,n = map(int,input().split())
for i in range(m,n+1):
    if Dis(i):
        print(i)

 

결과적으로 1부터 a의 제곱근까지 검사하게 함으로써 코드의 실행을 줄였다.

그리고 함수를 정의하여 만약 소수를 검사하는 과정에서 False가 나오면 출력을 안하고 

안 나누어 떨어지면 True를 사용하면 출력하도록 하였다.