[백준 1929] 소수 구하기 (+에라토스테네스의 체) python

문제

풀이

시간초과가 나와서 구글링해보니 에라토스테네스의 체를 이용해야 통과되는 문제이다.

에라토스테네스의 체

: 에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법이다.

• 숫자의 제곱근 까지만 약수의 여부를 검증하는 방식이다.

1. 먼저 2를 제외한 2의 배수를 제거

2. 3을 제외한 3의 배수 제거

3. 5를 제외한 5의 배수 제거... 

이런식으로 모든 구간에 대해 반복하면 소수만 남는다.

 

이것은

자신의 제곱근 까지만 약수의 여부를 검증하는 식으로 구현할 수 있다. (구글링을 통해 알게됨)

통과 된 풀이

def isPrime(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 isPrime(i):
        print(i)

시간 초과 된 풀이

m, n = map(int, input().split())
for num in range(m, n+1):
    if num > 1:
        for i in range(2, num):
            if num % i == 0:
                break
        else:
            print(num)