반응형
https://www.acmicpc.net/problem/2960
2960번: 에라토스테네스의 체
2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다.
www.acmicpc.net
문제
에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.
이 알고리즘은 다음과 같다.
- 2부터 N까지 모든 정수를 적는다.
- 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
- P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
- 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.
N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(1, K) < N ≤ 1000)
출력
첫째 줄에 K번째 지워진 수를 출력한다.
풀이
문제에 충실하게 풀었다
모든 정수를 적고, 가장 작은 수의 배수를 지웠다
C++로 먼저 풀려고 했는데 1시간 30분을 쏟았는데 안풀려서 열받아서 python으로 풀기 시작했고 11분만에 풀었다.
화가 나는 것이다.
python 코드
# 2960 에라노스테네스의 체
N, K = map(int,input().split())
arr = []
cnt = 0
ans = 0
for i in range(2, N+1):
arr.append(i)
min_num = arr[0]
while cnt < K:
i = 1
while min_num * i < N + 1:
if min_num * i in arr:
cnt += 1
arr.remove(min_num * i)
if cnt == K:
ans = min_num * i
i += 1
# print(arr)
if len(arr) > 0:
min_num = arr[0]
print(ans)
반응형
'study > 백준' 카테고리의 다른 글
[백준] 10814. 나이순 정렬 : python (0) | 2022.06.27 |
---|---|
[백준] 9012. 괄호 : python (0) | 2022.06.26 |
[백준] 4949. 균형잡힌 세상 : python (0) | 2022.06.22 |
[백준] 1181. 단어 정렬 : python (0) | 2022.06.21 |
[백준] 2304. 창고 다각형 : python : C++ (0) | 2022.06.21 |