文章目錄

原题链接 http://projecteuler.net/problem=10

Summation of primes

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

素数的和

10以下的所有素数的和是 2 + 3 + 5 + 7 = 17.

求2000000以下所有素数的和。

解答:
用筛法求得2000000以下的所有素数,之后求和

写成代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#!/usr/bin/python
# -*- coding:utf-8 -*-
'''
Created on 2013-5-5

@author: shilong
@email: long470884130@163.com
'''

from math import sqrt
def generate_prime(n):
'''得到[1,n]以内的素数'''
primes = [True for i in xrange(n + 1)]
primes[0] = primes[1] = False
for i in xrange(2,int(sqrt(n)) + 1):
if primes[i]:
s = i ** 2
while s <= n:
primes[s] = False
s += i
primes = [i for i in xrange(2,n + 1) if primes[i]]
return primes

if __name__ == "__main__":
n = 2000000
primes = generate_prime(n)
print sum(primes)

文章目錄