[백준 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=map(int,input().split(' '))
Key=False
li=[ i for i in range(2,n+1)]
cnt=0
# 2 3 4 5 6 
# 0 1 2 3 4 
 
key=False
while li:
    num=li[0]
    for i in li:
        if i % num ==0 :
            answer=i
            li.pop(li.index(i))
            cnt+=1
            if cnt==k:
                print(answer)
                key=True
    if key==True:
        break