https://www.acmicpc.net/problem/2960
2960번: 에라토스테네스의 체
문제 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다. 이 알고리즘은 다음과 같다. 2부터 N까지 모든 정수를 적는다. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다. N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에
www.acmicpc.net
소수를 찾는 알고리즘으로 유명한 에라토스테네스의 체를 풀어 보았습니다.
<문제에 적힌 에라토스테네스의 체 알고리즘>
- 2부터 N까지 모든 정수를 적는다.
- 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
- p를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
- 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.
<풀이>
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
def findKthPop():
del_cnt = 0
while len(data) != 0:
m = data[0]
cnt = 0
while cnt < len(data):
if data[cnt] % m == 0:
del_cnt += 1
if del_cnt == K:
return data[cnt]
data.pop(cnt)
cnt -= 1
cnt += 1
N, K = map(int, input().split())
data = list(range(2, N + 1))
print(findKthPop())
|
cs |
변수 m: 지우지 않은 수중 가작 작은 수 이자 소수이다.
변수 del_cnt: 지워지는 수의 순서
728x90
'난 이 분야 전문가야! > Algorithm' 카테고리의 다른 글
| [백준][C] 17070 파이프 옮기기 1 - 풀이 공유 (0) | 2020.05.04 |
|---|---|
| [백준][Python] 2294 동전2 - 풀이 공유 (0) | 2020.04.30 |
| [백준][Python] 1915 가장 큰 정사각형 - 풀이 공유 (0) | 2020.04.30 |
| [백준][C] 2994 내한 공연 - 풀이 공유 (1) | 2020.04.28 |
| [백준][Python] 11502 세 개의 소수 문제 - 풀이 공유 (0) | 2020.04.19 |