[백준] 1929번 문제 (에라토스테네스의 체, 소수 구하기) 파이썬(Python) 풀이

문제 내용

 

def is_prime(num):
    if num == 1:
        return False
    else:
        for i in range(2, int(num ** 0.5)+1):
            if num % i == 0:
                return False
        return True

m, n = map(int, input().split())

for i in range(m, n+1):
    if is_prime(i):
        print(i)

내가 작성한 코드

 

우선 처음 접근은 주어진 숫자 n에 대하여 2부터 n-1까지 나눠보면서 나눠지면 소수가 아니게 되므로 그 외의 수를 구하는 방식으로 접근했다.

 

하면서 예상은 했지만 이런 식으로 접근하게 되면 n이 1,000,000까지 주어질 수 있기 때문에 for문의 반복 횟수가 너무 커져 속도가 매우 느려진다.

 

따라서 이 문제는 에라토스테네스의 체의 방법을 이용하여 접근하여야한다.

 

출처 : https://terms.naver.com/entry.naver?docId=1179083&cid=40942&categoryId=32204

사실 되게 간단한 방법인 것 같은데 처음 이 방법을 구상했다는게 대단한 것 같다.

 

결과적으로 작성한 코드가 과연 에라토스테네스의 체의 방법으로 푼건지는 의문이 계속 남지만..

여튼 소수를 구하는 공식이 있었다.

 

바로 n이 주어질 때 n이 2부터 n의 제곱근까지 나눠지지 않으면 소수다.

 

왜냐하면

모든 숫자의 약수의 개수는 제곱근을 기준으로 왼쪽 오른쪽의 숫자가 같다.

 

숫자 14를 예로 들면 

1, 2, 제곱근(3.741...), 7, 14

 

9는 

1, 제곱근(3), 9

 

16은

1, 2 ,제곱근(4), 8, 16

 

이런식으로 숫자의 약수의 개수는 그 수의 제곱근을 기준으로 양쪽의 개수가 같다.

제곱근 기준 왼쪽의 숫자로 나누어지면 제곱근 기준 오른쪽의 숫자로도 나누어 진다.

따라서 오른쪽의 숫자는 배제하고 소수인지 판별할 수 있다.

 

소수인 17을 예로 들자면

1, 제곱근(4.1231...), 17

 

제곱근 까지의 수로 나눠도 나눠지지 않는다.

 

결과적으로 n이 소수인지 아닌지 for문을 주어진 숫자 n^1/2 까지만 반복하면서 구하면 시간을 두배(?)는 더 절약할 수 있다.

 

태클은 언제나 환영합니다..