[Algorithm] 1일1솔 - 백준 2960 에라토스테네스의 체 (python3)

문제링크

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

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

 

문제풀이

n, k = map(int, input().split())
sieve = [True] * (n+1)
m = int(n**0.5)
chk = []
for i in range(2,m+1):
    if sieve[i] == True:
        chk.append(i)
        for j in range(2*i, n+1, i):
            sieve[j] = False
            if j not in chk:
                chk.append(j)
chk += [i for i in range(m+1,n+1) if sieve[i] == True]
print(chk[k-1])

에라토스테네스의 체를 거쳐 완료된 소수가 담긴 리스트를 구하는 것이 아니라, 그 과정을 이해하고 그 과정에서 체크되는 소수와 걸러지는 소수의 배수들을 차례로 체크해야 하는 문제이다.

n 의 최댓값이 1000이라서 시간복잡도 문제는 크게 고려하지 않아도 되기에 chk 리스트를 선언해서 에라토스테네스의 체의 소수와 그 배수들을 담았다.

그 후에 chk에서 k번째로 담긴 (인덱스로 치면 k-1) 수를 출력했다.

 

뭔가 배열에 담고 체크하는 것보다 카운팅을 바로 하면 시간복잡도에서도 효율적일 것 같아 이후에 배열을 선언하지 않는 방법으로도 시도해봐야겠다.