プロジェクトオイラー10.

この記事の所要時間：約 1分23秒

No.10 Summation of primes

問題.

Q. 10 未満の素数の和は,

$\begin{equation*} 2+3+5+7 = 17 \end{equation*}$

です. では, 2,000,000 未満の素数の和はいくつになるか.

考え方とプログラム例(Python)

実際に 2,000,000 未満の素数を「エラトステネスの篩」を用いて求め, 和を求めていきます.

import math
N = 2000000
num = [0]*N
num[0] = 1
for i in xrange(N):
	if num[i] == 0:
		if i+1 > math.sqrt(N):
			break
		n = 2*(i+1)
		while n <= N:
			num[n-1] = 1
			n += (i+1)
#Sum = sum(filter(lambda i : num[i-1] == 0, xrange(1, N+1)))
Sum = sum([i + 1 for i  in xrange(N) if num[i] == 0])
print Sum

import math

N = 2000000

num = [0]*N

num[0] = 1

for i in xrange(N):

if num[i] == 0:

if i+1 > math.sqrt(N):

break

n = 2*(i+1)

while n <= N:

num[n-1] = 1

n += (i+1)

#Sum = sum(filter(lambda i : num[i-1] == 0, xrange(1, N+1)))

Sum = sum([i + 1 for i in xrange(N) if num[i] == 0])

print Sum

エラトステネスの篩の部分は,

自然数 $i$ が素数 ⇔ $num[i-1]=0$

素数でない ⇔ $num[i-1]=1$

となるように実装しています.

配列 $num[]$ にすべて 0 が入った状態から始めることで, エラトステネスの篩の最後の部分( $\sqrt{2,000,000}$ を超えた時点で残っている数はすべて素数となる) を特に実装しなくて済みます.

最後に $num[i-1]=0$ である $i$ の和を求める部分は,

filter を利用した方法(コメントアウトしてあります)
list の内包表記を利用した方法

の2通りを書いてみました.

答えはこの下の行にあります. 反転してください.

A. 142913828922

プロジェクトオイラー10.

No.10 Summation of primes

問題.

考え方とプログラム例(Python)

共有:

関連

関連記事