[Algorithm] [Python & Swift] 백준/BOJ - 2960 _ 에라토스테네스의 체

2960 - 에라토스테네스의 체

 

문제

---

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

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

2부터 N까지 모든 정수를 적는다.
아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.
N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.

 

입력

---

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

 

출력

---

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

 

제출 코드

---

Swift

let input = readLine()!.split(separator: " ").map { Int($0)! }
let n = input[0]
let k = input[1]
var cnt = 0
var arr = Array(repeating: true, count: n+1)

for i in 2..<n+1 {
    for j in stride(from: i, to: n+1, by: i) {
        if arr[j] {
            arr[j] = false
            cnt += 1
            if cnt == k {
                print(j)
                break
            }
        }
    }
}

 

Python

from sys import stdin

n, k = map(int, stdin.readline().split())
arr = [True] * (n+1)
cnt = 0

for i in (2, n+1):
    for j in range(i, n+1, i):
        if arr[j]:
            arr[j] = false
            cnt += 1
            if cnt == k:
                print(j)
                break

 

문제풀이

---

그 유명한 소수찾기 알고리즘 "에라토스테네스의 체"이다.

에라토스테네스의 체 흐름은 아래와 같다.

1. 2부터 N 까지의 모든 수를 나열한다.
2. 가장 작은 소수를 찾아 해당 소수의 배수를 모두 지운다. (ex: 2가 가장 작은 소수이므로 4, 6, 8, 10, .... 을 모두 삭제)
3. 다음으로 가장 작은 소수를 찾아 이를 반복한다.

위 2~3 과정을 반복하면 원하는 구간 내 모든 소수를 구할 수 있다.

이번 문제는 위 알고리즘을 이용해 k번쨰로 지워지는 숫자를 찾는 방법이다.

2~N 까지의 구간을 만들어놓고 이를 순회하면서 True 값이 발견되면 해당 인덱스의 배수 원소들을 모두 False로 변경하며 배수들을 제거한다.

제거하는 원소를 카운팅하다가 k가 되면 이를 출력하고 종료한다.