Pythonでエラトステネスの篩（ふるい）を実装してみる-ABC084

本記事ではエラトステネスの篩（ふるい）をPythonで実装していきます。

実際に問題を解きながらエラトステネスの篩の動きを確認していきましょう。

エラトステネスの篩とは

エラトステネスは古代ギリシャの学者で、数学や天文学にとどまらず哲学や文献学などの多岐にわたる分野で活躍したすごい人です。

特に、地球の大きさを初めて定量的に測定したことや、素数の判定法を発明したことで有名です。

この素数判定法が今回紹介する「エラトステネスの篩」です。

エラトステネスの篩は以下のような流れで素数を判定します。

1. 2以上n以下の整数を並べる
2. 未使用のものから一番小さいものを選び、その倍数をふるい落とす
3. ②の操作を繰り返し残ったものが素数

文章だけではわかりにくいと思うで、実際に問題を解いて動きを確認してみましょう。

例題

本記事では例題として以下の問題を扱います。
atcoder.jp

問題文

「 も も素数」を満たす奇数 を 2017に似た数 とします。
個のクエリが与えられます。
クエリ では奇数 , が与えられるので、 かつ 2017に似た数 となる奇数 x の個数を求めてください。

制約

• 
• 
• ,は奇数
• 入力は全て整数

実装

この問題は範囲内 () の素数を列挙し、その中から「 も も素数」を満たすものを累積和を用いて数え上げれば解くことができます。
nashidos.hatenablog.com

素数を列挙する際に先ほど述べた「エラトステネスの篩」を利用します。

以下が実装したコードです。

import math
from itertools import accumulate

# エラトステネスの篩
def eratosthenes(n): 
    prime_list = []
    num_list=[i for i in range(2, n+1)] # 2以上n以下の整数を並べる
    limit = math.sqrt(n)
    while True:
        if limit <= num_list[0]:
            return prime_list + num_list
        prime_list.append(num_list[0])
        num_list = [e for e in num_list if e % num_list[0] != 0] # 倍数をふるい落とす

max_lr = 100000
er_list = eratosthenes(max_lr)

count = [0] * max_lr
for i in range(len(er_list)):
    if (er_list[i]+1)//2 in er_list:
        count[er_list[i]] = 1

# 累積和            
count = list(accumulate(count)) 

Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    print(count[r]-count[l-1])

実装の流れは以下の通りです。

まずまでの素数をエラトステネスの篩を用いて求めます。

次に、「 も も素数」を満たすものを数え上げるためのリストを作成します。

数え上げるために条件を満たすものにを代入します。

そして、 の範囲で毎回計算していると間に合わないので累積和をとります。

あとは累積和のリストをもとに簡単に答えを求めることができます。

まとめ

本記事ではエラトステネスの篩を用いて実際に問題を解いていきました。

今回実装したコードは読みやすさ重視で書いたのでスピードは遅めです。
ぜひ高速化してみてください。

おわり