[백준] 2960번_에라토스테네스의 체 (Python/파이썬)

https://www.acmicpc.net/problem/2960

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번째 지워진 수를 출력한다.

해결방법

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

위의 주어진 해결방법 순으로 그대로 코드에 옮겨서 문제를 해결했다.

먼저,  array에 숫자가 존재하면 True 값을 부여하고, 숫자를 제거하면 False로 바꿔가며 코드를 수정했다.

여기서 기존 에라토스테네스의 체의 알고리즘과 다른 점은 지우지 않은 수 중 가장 작은 수(소수)를 찾는 것인데,

소수 P 또한 지운다는 것이다. 그 후  P의 배수를 크기 순서대로 지우는 것이다.

K번째 지운 수를 찾기 위해 배열에 담았고, 인덱스 수에 해당되는 값을 도출해내어 답을 출력했다.

 

n, k = map(int, input().split())
array = [True for i in range(n+1)]
count = []
for i in range(2, n+1):
    if array[i] == True:
      array[i] = False
      count.append(i)
      j = 2
      while i * j <= n:
        if array[i*j] == True:
          array[i*j] = False
          count.append(i*j)
        j += 1
        
print(count[k-1])