[BOJ] [Python] 2960번 : 에라토스테네스의 체

소수의 배를 제거하면서 k번째를 찾으면 된다.

 

dp 리스트로 중복방지를 하며, K번째를 찾을 수 있게 카운트해 줬다.

예를 들어, 6은 2의 3의 공통배수이다. 따라서 중복제거를 피해야 한다.

 

 

import sys, math

input = sys.stdin.readline

n, k = map(int, input().split())

sosu = []

for num in range(2, n + 1):
    check = True

    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:
            check = False
            break

    if check:
        sosu.append(num)


def main():
    cnt = 0

    dp = [0] * (n + 1)

    for num in sosu:
        for i in range(1, (n // num) + 1):

            cal = num * i

            # print(cal, num, i)
            if dp[cal] == 0:

                dp[cal] = 1
                cnt += 1

                if cnt == k:
                    return cal
print(main())