[파이썬 / 백준 2960번] 에라토스테네스의 체

 

 

 

https://www.acmicpc.net/problem/2960

이 문제를 마지막으로 에라토스테네스의 체 원리를 이해했다.

 

728x90

def aes(N,K):
    cnt=0
    a=0
    S=[True]*(N+1)
    for i in range(2,N+1):
        if S[i]:
            for j in range(i,N+1,i):
                if S[j]:
                    S[j]=False
                    cnt+=1
                    if cnt==K:
                        a=j
                        break
        if cnt==K:
            break
    return a
N,K=map(int,input().split())
ans=aes(N,K)
print(ans)