[Algorithm] 특정 범위 내의 소수 찾기 - 에라토스테네스 체

소수

양의 약수를 두 개만 가지는 자연수

Sieve of Eratosthenes

고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법. 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다.

특정 범위가 주어지고 그 범위 내의 모든 소수를 찾아야 하는 경우, 아직까지 소수들 간의 연관성(=소수를 생성할 수 있는 공식)이 나오지 않았으므로 에라토스테네스의 체보다 빠른 방법이 없다.

만약 100까지의 소수를 찾는다고 하면 100의 길이를 갖는 배열을 만들어 0으로 초기화 시킨후
2의 배수를 체크하여 1로 변경한다. 이후 1이 들어가 있는 경우 소수가 아님을 알 수 있다.
그다음 3의 배수를 체크하여 1로 변경한다. 이때 이미 1이 들어있는 값이면 그냥 넘어간다.
이 과정을 100까지 반복하면 된다.
처음 해당 값을 확인 했을 때 0이 있으면 그 숫자는 소수임을 알 수 있다.

알고리즘

1. 입력받은 범위의 배열을 생성하여 값을 0으로 초기화한다.
2. 2부터 시작해서 특정 숫자의 배수에 해당하는 숫자들을 모두 지운다. (1로 변경한다.)
3. 이미 지워진 숫자의 경우(1인 경우) 건너 뛴다.

N = int(input())
num = [0] * (N + 1)
cnt = 0
for i in range(2, N + 1):
    if num[i] == 0:
        cnt += 1
        for j in range(i, N + 1, i):
            num[j] = 1
print(cnt)