【Project Euler】Problem 10: 素数の合計

• 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。

問題 10． 素数の合計

原文 Problem 10: Summation of primes

問題の要約：$2*10^6$未満の素数の合計を求めよ

安易ですが。sympyのprimerangeはこの手の問題を解くときに便利なので。

from sympy import primerange

plist = list(primerange(1,2*10**6))
print(f"Answer : {sum(plist)}")

Lucy DPを用いて高速化

このアルゴリズム詳細は素数の個数や和を高速に計算できるLucy DPをやさしく説明で解説しています。

N = 10**6
r = int(N**0.5)
V = [N//i for i in range(1,r+1)]
V += list(range(V[-1]-1,0,-1))
S = {i:i*(i+1)//2-1 for i in V}
for p in range(2,r+1):
    if S[p] == S[p-1]: continue # p is not prime
    sp = S[p-1]  # sum of primes < p
    for v in V:
      if v < p**2: break
      S[v] -= p*(S[v//p] - sp)
print(f"# Answer : {S[N]}")

計算時間の比較

N	$10^2$	$10^6$	$10^{8}$	$10^{10}$	$10^{12}$
primerange	0.01s	2.13s	195s	-	-
Lucy DP	0.01s	0.03s	0.91s	13.72s	380s

（開発環境：Google Colab）