[백준][Python] 2960번 에라토스테네스의 체

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

 

코드

N, K = map(int,input().split())
n_list = [False]*(N+1)
cnt = 0
for i in range(2,N+1):
    if n_list[i] == False:
        for j in range(i,N+1,i):
            if n_list[j] == False:
                n_list[j] = True
                cnt += 1
                if cnt == K:
                    print(j)

 

설명

n_list라는 리스트를 만들어 처음 값을 False로 둔다.

2부터 차례대로 자신의 배수를 모두 지워나가서 리스트값을 True로 바꿔주면 결국 i값 중 소수만 (n_list[i] == False)라는 if문을 통과하게 된다. True로 하나씩 바꿔주면서 cnt 값을 1씩 증가시켜주고 만약 K값과 같아지면 현재 지워준 수를 출력해준다.