에라토스테네의 체 알고리즘(소수 나열)

정해진 범위 내에서 소수 구하기

1. 2부터 N까지 존재하는 모든 자연수를 나열한다.
2. 나열된 숫자 중에서 가장 작은 수를 x로 지정한다.
3. 나열된 숫자 중에서 x의 배수를 모두 제거한다. (이때, x는 제거하지 않는다)
4. 더 이상 반복할 수 없을 때까지 2번과 3번을 반복한다.

import  math
n = 30
array = [True for i in range(n+1)] #모두 소수라 가정
print(array)
for i in range(2, int(math.sqrt(n) + 1)): #2부터 (n+1)의 제곱근 까지의 모든수를 확인한다.
    if array[i] == True:
        j = 2
        while i * j <= n:
            array[i * j] = False
            j += 1
print(array)

for i in range(2, n+1):
    if array[i]:
        print(i, end = ' ')