ABC084-D Pythonでの「エラトステネスの篩」を用いた解法 - Qiita

「エラトステネスの篩 (ふるい)」という手法を使うと、素数テーブルを高速に作成することができます。 そのテーブルとは、配列のインデックス $i$ が素数だった場合、その要素が True となる配列のことです。 この問題では作成した素数テーブルを用いて、「2017に似た数」かどうかを判定し、累積和 という手法を用いることでより高速に「2017に似た数」が何個あるか数えられます。 コード Q = int(input()) lr = [list(map(int, input().split())) for _ in range(Q)] N = 10 ** 5 prime = [True] * (N + 1) prime[0] = prime[1] = False # 素数テーブルの作成 (エラトステネスのふるい) for i in range(2, N + 1): if prime[i]: fo