欧拉工程第十解

| Comments

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

Find the sum of all the primes below two million.

题目越来越变态,开始好玩儿了。

第七解里的算法在这里算是废了,一万个素数都算得那么费劲,两百万以下的素数有十几万个,不得不用筛选法了。

普通的筛选效率也不行,当初就是因为这个原因才没用它。不过优化过的筛选法就很奇妙了,下面是Lua的实现:

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
27
require('math')

local limit = 2000000

local primes = {}
for i=1,limit do
    table.insert(primes,true)
end
primes[0] = false
primes[1] = false

for i=0,math.floor(math.sqrt(limit)) do
    if primes[i] then
        for j=math.pow(i,2),limit,i do
            primes[j] = false
        end
    end
end

local sumVal = 0
for i,j in ipairs(primes) do
    if j then
        sumVal = sumVal + i
    end
end

print(sumVal)

在我这里两秒半就出结果了,Python的表现也不错,四秒半出结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from math import sqrt

limit = 2000000
primes = [True for i in range(0,limit)]
primes[0] = False
primes[1] = False

for i in range(1,int(sqrt(limit))+1):
    if primes[i]:
        for j in range(i**2,limit,i):
            primes[j] = False

sumVal = 0
for i in range(len(primes)):
    if primes[i]:
        sumVal += i

print sumVal