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

📕 문제

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

이 알고리즘은 다음과 같다.

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

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

 

[입력]

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(1, K) < N ≤ 1000)

 

[출력]

첫째 줄에 K번째 지워진 수를 출력한다.

 

💡 풀이법

: 문제에서 시키는대로 고대로 따라갔다.

 

1. prime이라는 리스트에 2부터 N까지 모든 정수를 넣는다.

2. 가작 작은 수를 꺼내서 소수인지 판단한다. ( is_prime 함수 이용 )

3. 소수이면 그 배수를 계속 지워나간다.

4. 지워나가면서 계속 cnt를 1씩 증가시켜준다.

5. 만약 cnt가 문제에서 요구하는 K와 같으면 그때의 수를 출력한다.

 

def is_prime(n):
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

def eratostenes(N, K):
    cnt = 0
    prime = [i for i in range(2,N+1)]
    while prime:
        n = prime[0]
        if is_prime(n):
            m = 1
            while n*m <= N:
                if n*m in prime:
                    prime.remove(n*m)
                    cnt += 1
                    if cnt == K:
                        return n*m
                m += 1

N, K = map(int, input().split())
print(eratostenes(N, K))