[Python][백준 2960] 에라토스테네스의 체

Date: 2025.01.30 Updated: 2025.02.01

카테고리: Python Coding Test

태그: coding test 백준 2960 소수 에라토스테네스의 체 python

🔢 에라토스테네스의 체 문제 풀이

백준 2960번 에라토스테네스의 체 문제의 파이썬 풀이

📝 문제 설명

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 알고리즘이다. 이 알고리즘은 다음과 같다.

2부터 N까지 모든 정수를 적는다.
아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하자. 이 수는 소수이다.
P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

N과 K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.

💡 풀이

이 문제는 에라토스테네스의 체 알고리즘을 구현하고 수를 지울 때마다 카운트를 증가시켜 K번째로 지워지는 수를 찾아야 한다.

🔍 코드 설명

N까지의 수를 저장할 배열을 생성한다.
2부터 N까지 순회하면서:
- 현재 수가 지워지지 않았다면, 그 수와 그 수의 배수들을 순서대로 지운다.
- 수를 지울 때마다 카운트를 증가시킨다.
- K번째로 지워지는 수를 찾으면 출력하고 종료한다.

✨ 참고

원래의 에라토스테네스의 체와 달리 수를 지우는 순서가 중요하다.
배수를 지울 때는 작은 수부터 순서대로 지워야 한다.
이미 지워진 수는 건너뛰어야 한다.

🎯 주의사항

지워지는 순서가 중요하므로 정확한 순서로 구현해야 한다.
이미 지워진 수는 다시 지우지 않는다.

📝 코드

import sys

def sieve(n, k):
    A = [0] * (n + 1)
    count = 0
    result = 0
    
    for i in range(2, n + 1):
        A[i] = i

    # 에라토스테네스의 체
    for i in range(2, n + 1):
        if A[i] == 0:
            continue
        for j in range(i, n + 1, i):
            if A[j] != 0:
                count += 1
            if (count == k):
                print(A[j])
                return
            A[j] = 0

n, k = map(int, sys.stdin.readline().split())
sieve(n, k)

감자