[SWEA / PYTHON] 3131. 100만 이하의 모든 소수

result = []

N = 1000000


def prime_list(N):
    sieve = [True] * N

    m = int(N**0.5)

    for i in range(2, m + 1):
        if sieve[i] == True:
            for j in range(i + i, N, i):
                sieve[j] = False

    return [i for i in range(2, N) if sieve[i] == True]


print(*prime_list(N))

풀이.

이 문제는 에라토스테네스의 체 공식으로 문제를 풀어야 한다.

2 부터 N 까지의 수열이 있을 때, 자신을 제외한 2의 배수를 전부 제거해주고, 그 다음 3의 배수를 전부 제거, 4의 배수를 제거 .... N의 제곱근 까지 배수를 제거해주면, 남아 있는 수는 모두 1과 자신 뿐인 소수가 된다.

이 때 N의 제곱근 까지만 구한는 이유는, N의 최대 약수가 N의 제곱근이므로, 모든 수를 체크할 수 있다.