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

📖 문제

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

💻 내 코드

n,k=map(int, input().split())
mlist=[i for i in range(2, n+1)]
nums=[]

while len(mlist)!=0:
    p=min(mlist)
    nums.append(p)
    mlist.remove(p)
    
    for m in mlist:
        if m%p==0:
            nums.append(m)
            mlist.remove(m)

print(nums[k-1])

💡 추가

• 에라토스테네스의 체: N보다 작거나 같은 모든 소수를 찾는 알고리즘
• 문제에서는 남아있는 수들 중 가장 작은 수를 지웠지만 실제로는 지우지 않고, 마지막에 남아있는 수가 소수이다

다른 사람 코드

N, K = map(int, input().split())
tmp = 0
nums = [True] * (N + 1)
for i in range(2, N + 1):
    for j in range(i, N + 1, i): # i의 배수이므로 i부터 i씩 건너뜀
        if nums[j] != False:
            nums[j] = False
            tmp += 1
            if tmp == K:
                print(j)