[Python/파이썬] 백준 알고리즘 1929번 - 소수 구하기

 

 

 

<풀이 - 시간초과 오답>

M, N = map(int, input().split())

for i in range(M, N+1):
    primeNum = True
    if i == 1:
        primeNum = False
    else:
        for j in range(2, i):
            if i % j == 0:
                primeNum = False
                break
    if primeNum:
        print(i)

처음엔 위와 같이 풀었었다.

숫자 i 하나에 대해 2부터 i-1까지 나눠보면서 0으로 나누어 떨어지면 소수가 아니므로 이를 제외하는 방식으로 코드를 짰었다.

그러나 1929 문제에서 이 방식은 시간초과가 떴다.

 

그래서 구글링을 해보니 '에라토스테네스의 체'를 이용해 시간을 단축해야한다고 한다.

 

에라토스테네스의 체는 가장 대표적인 소수 판별 알고리즘이다.

에라토스테네스의 체는 특정한 숫자의 제곱근까지만 약수의 여부를 검증하는 방식이다.

이러면 일반적인 소수 판별 알고리즘의 시간복잡도인 O(N)에서 O(N^(1/2))로 줄게되어 시간이 단축된다.

 

제곱근까지만 약수의 여부를 검증해도 소수인지 아닌지 알 수 있는 이유는 6과 같은 수의 경우 2 * 3 = 3 * 2로 대칭을 이루기 때문이다.

 

<풀이 - 에라토스테네스의 체(정답)>

# 인자로 들어온 수의 제곱근까지만 확인하여 소수인지 아닌지를 검증하는 함수
def isPrime(num):
    if num == 1:
        return False
    else:
        for n in range(2, int(num**0.5)+1):
            if num % n == 0:
                return False
        return True

M, N = map(int, input().split())

for i in range(M, N+1):
    if isPrime(i):
        print(i)

여기선 따로 isPrime()이라는 함수를 만들어 인자로 들어온 수의 제곱근 까지만 소수인지 아닌지를 확인하게 하였다. 소수일 경우 True가 반환되고 이 경우 print된다.

(1은 소수가 아니므로 바로 제외시킨다.)

 

 

 

<핵심 정리>

1. 일반적인 소수 판별 알고리즘의 속도를 높히는 가장 대표적인 방법으로 '에라토스테네스의 체'가 있다.

2. 에라토스테네스의 체 소수 판별 알고리즘은 검증하고자 하는 수의 제곱근까지만을 검증해 소수인지 아닌지 판별하는 방식이다.

3. 이 에라토스테네스의 체는 한 두 개의 소수를 판별하는 것이 아니라 대량의 소수를 한꺼번에 판별하고자 할 때 사용한다.