白駿解題-エラトネスの体2960号

📜 問題を理解する
エラトネスのふるいはN以下の素数をすべて探す有名なアルゴリズムである.
このアルゴリズムは以下の通りです.
2からNまですべての整数を書き出します.
クリアされていない数の最小数を探します.これはPと言います.この数は小数です.
Pをクリアし、クリアされていないPの倍数をサイズ順にクリアします.
もしあなたがまだすべての数字を削除していないならば、再び第2段階に入ります.
N,Kが与えられたとき,K回の削除数を求めるプログラムを作成してください.
💡 問題の再定義
エラトステネスのふるいからK番目に消された数を求めた.
▼▼▼計画作成
エラトネスの体のアルゴリズムに従って消せばいいです.ただ上は2*iから消すのではなく、iから消すのです.つまり、2,3も少数ですが、削除されることを考えてプログラミングしましょう.
💻 計画の実行

if __name__ == '__main__':
    N, K = map(int, input().split())
    prime_list = [False, False] + [True] * (N - 1)

    cnt = 0
    for i in range(2, N + 1):
        if prime_list[i]:
            for j in range(i, N+1, i):
                if prime_list[j]:
                    prime_list[j] = False
                    cnt += 1
                    if cnt == K:
                        print(j)
                        exit(0)

🤔 振り返る
エラトネスの体を知っていれば、簡単に解けます.