백준 (boj) 파이썬 - 2960번 : 에라토스테네스의 체

문제 링크 : https://www.acmicpc.net/problem/2960

2960번: 에라토스테네스의 체

 

 

 

에라토스테네스 개념 : https://infinitt.tistory.com/232

알고리즘 (1) - 수학 : 유클리드 호제법 , 에라토스테네스의 체 (나머지 연산, 최대 공약수, 최소공배수, 소수)

 

 

범위도 작아 시간초과 할 일도 없고 코드구현도 간단했다. 

 

파이썬 코드

N, K = map(int,input().split())

cheak = [False for _ in range(N+2)]
cnt = 0
for i in range(2,N+1):
    if cheak[i] == False:
        for j in range(i, N+1, i):
            if cheak[j] == False:
                cheak[j] = True
                cnt += 1
                
                if cnt == K :
                    print(j)
                    break