에라토스테네스의 체

에라토스테네스의 체

 

 

임의의 자연수 n에 대해 그 이하의 소수를 찾는 가장 간단하고 빠른 방법이다. 

1. 2부터 N까지의 모든 자연수를 나열한다.
2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
3. 남은 수 중에서 i의 배수를 모두 제거한다.(i는 제거하지 않는다.)
4. 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다.

def Eratosthenes(n):
	arr = [1 for i in range(1, n+1)]
	arr[0] = 0
    arr[1] = 0
    for i in range(2, int(math.sqrt(len(arr)))):
        if arr[i] == 1:
            for j in range(i+i, len(arr), i):
                arr[j] = 0
	return arr

n = int(input())
arr = Eratosthenes(n)
for i in range(1, n+1):
    if arr[i] == 1:
        print(i)