[백준 1929] 소수 구하기 / 파이썬 + 에라토스테네스의 체

실버3에 랭크된 것을 보니 평범한 소수 구하기는 아닐 것 같아서 알고리즘 분류를 확인해 보았다.

에라토스테네스의 체라고 적혀있다.

에라토스테네스의 체

임의의 자연수 n에 대해 그 이하의 소수를 모두 찾는 방법이다.
1, 2/3/5/7/11..로 나누다보면 소수만 남는다.

n의 제곱근( $\sqrt{N}$ , n ** 0.5)을 구하고, 제곱근까지의 약수를 구한다.
여기서 제곱근보다 작거나 같은 수 까지만 나누어 약수와 소수가 아닌 수를 모두 제거할 수 있다. (N이 제곱근보다 작은 약수로 나누어 떨어지기 때문에 제곱근을 넘어선 수는 확인할 필요가 없다.)

from collections import deque
import sys

def check_prime(arr):
    for n in arr:
        if n < 2:
            continue

        is_prime = 1
        for j in range(2, int(n ** 0.5) + 1):
            if n % j == 0:
                is_prime = 0
                break

        if is_prime:
            print(n)

input = sys.stdin.readline

M, N = map(int, input().split())
primes = deque(x for x in range(M, N + 1))
check_prime(primes)

오래걸려서 다른사람들의 풀이도 확인해 보았다.
시간이 적게 걸린 사람들의 풀이를 확인해보니 숫자 그대로가 아니라 리스트에 T/F를 저장해 두었다. T/F로 저장한 경우가 더 빠른 이유는 계산을 덜하기(%, 중복계산..) 때문이 크다.

풀이를 보니 공통적으로 아래의 코드를 사용했는데

for j in range(i * i, N + 1, i):
	is_prime[j] = False

i*i부터 하는 이유는 5를 예로 들자면

i
5 * 1	5
5 * 2	10
5 * 3	15
5 * 4	20
5 * 5	25

이므로, i * (i - 1)까지는 이미 없어진 상태이고, i * i가 새로 나타나는 수이기 때문에 여기서부터 확인하면 된다.

from collections import deque
import sys

input = sys.stdin.readline

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

is_prime = [True] * (N + 1) #0~N -> N+1개 생성
is_prime[0] = is_prime[1] = False #0과 1 처리

for i in range(2, int(N ** 0.5) + 1):
    if is_prime[i]:
        for j in range(i * i, N + 1, i): #i*i의 배수 모두 제거
            is_prime[j] = False

for i in range(M, N + 1):
    if is_prime[i]:
        print(i)