[백준/파이썬/수학] 2960번 에라토스테네스의 체 코딩테스트 연습풀이 실버4

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

 

예제 입력 1

7 3

 

예제 출력 1

6

 

예제 입력 2

15 12

 

예제 출력 2

7

 

예제 입력 3

10 7

 

예제 출력 3

9

2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다.

 

정답

n, k = map(int, input().split())

arr = list(range(2,n+1))
answer = []

for tmp in range(2,n+1):
    for i in arr:
        if i%tmp == 0 and i not in answer:
            answer.append(i)
print(answer[k-1])

1. n, k를 입력

2. arr 2부터 n까지 입력

3. 이중 for문으로 숫자를 append

4. answer[k-1]로 출력

 

위의 코드는 k번째까지만 실행하는게 아니고 전체를 다 돌리는 것이라서 시간초과가 뜰경우 줄여주려고 했는데 시간초과가 안떴기 때문에 그대로 진행하였습니다~