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

2960 에라토스테네스의 체

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

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

[정답]

import sys
N, K = map(int, sys.stdin.readline().split())
e = [True for i in range(N+1)]
e[0], e[1] = False, False
cnt = 2
c = 0
while(c<K):
    if e[cnt]:
        for j in range(cnt, N+1, cnt):
            if e[j]:
                e[j] = False
                c += 1
                if c == K:
                    print(j)
    cnt += 1

.

.

.

[풀이]

에라토스테네스의 체

그리스 수학자가 발견한 소수 찾는법이라 한다.

 

N까지 수의 리스트를 만들어 준 후,

cnt의 배수를 False로 바꾸며 진행한다.

바꿀 때마다 증가하는 c가 K와 같아지면 답을 출력하고 종료한다.

 

무식하게 N번까지 다 하지 않으려고 for()가 아닌 while()을 사용해봤다.