📌 에라토스테네스의 체 ?

여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표적인 알고리즘
N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다.

2부터 N까지의 모든 자연수를 나열한다.
남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다
남은 수 중에서 i의 배수를 모두 제거한다 (i는 제거 안함)

import math

n = 1000
array = [True for i in range(n+1)]

for i in range(2, int(math.sqrt(n))+1):
    if array[i] == True:
        j = 2
        while i * j <= n:
            array[i*j] = False
            j += 1
for i in range(2, n+1):
    if array[i]:
        print(i, end=' ')