에라토스테네스의 체

” 에라토스테네스의 체 “ 그래서 뭔가요?

설명 :

1. 1은 건너 뛴다.

2. 2는 소수이다. 2의 배수는 모두 제외,

3. 3은 소수이다. 3의 배수는 모두 제외,

4. 4는 2의 배수라서 이미 제외

5. 5는 소수이다. 5의 배수 모두 제외,

6. 6은 2와 3의 배수이다. 이미 제외

7. 7은 소수이다. 7의 배수 모두 제외,

8. 8은 2와 4의 배수이다. 이미 제외

9. 9는 3의 배수이다

# num 까지의 소수 구하기
num = int(input())
arr = [True]*num
# num의 약수는 루트num이 최대
for i in range(2, int(num**0.5)+1):
    if arr[i]:
        for j in range(i+i, num, i):
            arr[j] = False

for i in range(2, num):
    if arr[i]:
        print(i, end =' ')