[파이썬]백준 2960 에라토스테네스의 체

링크

백준 2960 에라토스테네스의 체

원래는 해당 문제를 풀생각이 아니었다.
17103 골드바흐파티션 문제를 풀려 했으나 도저히 소수를 효율적으로 구하는 방법을 모르겠어서 검색을 했다.

'에라토스테네스의 체'를 이용하면 소수를 쉽게 구할 수 있다는 것을 알았고 코드를 직접 짜봤다.
(이 코드와 에라토스테네스의 체의 설명은 글 하단에 작성하겠다.)

나아가 좀더 체득하기 위해 관련문제인 해당문제를 풀었다.
소수를 구하는게 아니므로 소수를 따로 저장해 줄 필요는 없다.
또한, 문제에선 소수마저 카운트로 치기 때문에 해당 부분만 주의해서 구현해주면 된다.

정답 코드

N, K = map(int, input().split())
tmp = 0
sieve = [True] * (N + 1)
for i in range(2, N + 1):
    for j in range(i, N + 1, i):
        if sieve[j] != False:
            sieve[j] = False
            tmp += 1
            if tmp == K:
                print(j)

알게된 것👨‍💻

• 에라토스테네스의 체

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다.
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다.
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다.
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다.
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

• 코드

n = 1000
sieve = [False, False] + ([True] * (n - 1))
primes = []

for i in range(2, n + 1):
    if sieve[i]:
        primes.append(i)
    for j in range(i * 2, n + 1, i):
        sieve[j] = False

print(primes)

• 코드설명

1. 인덱스 0번과 1번을 제외한 나머지를 True로 하는 리스트를 초기화 한다.
2. 인덱스 2번부터 리스트의 가장 마지막 인덱스 까지 반복한다.
3. 만약에 해당 인덱스의 값이 True라면 해당 인덱스를 소수로 여기고 저장해준다.
4. 해당 인덱스의 배수를 전부 False로 바꿔준다.