10以内的素数之和是 2 + 3 + 5 + 7 = 17.
求两百万以内的素数之和。
分析:关键是寻找一个高效的筛法,用下面这个是不行的:
sieve (x:xs) = x: sieve [ n | n<-xs,n`mod`x/=0]
注意到,8/2=4和8/4=2是意义重复的除法运算,因此要验证8是否是素数只要用8与[2,根号8]之间的自然数做除运算就行了。
一般化:一个自然数n是素数,当它无法被[2,根号n]之间的自然数整除。
改进:一个自然数n是素数,当它无法被[2,根号n]之间的素数整除。
利用这个规律写出的筛法quickSieve:
sieve [] numbers = numbers
sieve (p:ps) numbers = sieve ps (filter (\n->n`mod`p/=0) numbers)
quickSieve ps primes limit
| lp^2 > limit = []
| otherwise = addPrimes ++ quickSieve pss (tail newPrimes) limit
where lp = last ps
hp = head primes
pss = ps ++ [hp]
numbers = [lp^2+1 .. minimum [hp^2,limit] ]
addPrimes = sieve pss numbers
newPrimes = primes ++ addPrimes
answer = sum ([2,3]++quickSieve [2] [3] 100)
答案是142913828922