에라토스테네스의 체 구현

출처 : 위키피디아

 

import sys

n = int(sys.stdin.readline()) # 수 입력
nums = [True] * (n + 1) # 전체 수에 해단 True / False
m = int(n ** 0.5) # n의 제곱근

for i in range(2, m + 1):
    for j in range(i*2, n, i):
        if nums[j] == True: # i의 배수 전부 지움(i 보다 큰 수)
            nums[j] = False

for i in range(2, n):
    if nums[i] == True: # True인 element의 인덱스(소수) 출력
        print(i, end=" ")