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。
求所有小于两百万的质数的和。
我们可以使用在 problem 7 中写过的素数判定函数:
(defun eu7-isprime (n)
(cond
((<= n 1) nil)
((< n 4) t)
((zerop (% n 2)) nil)
((< n 9) t)
((zerop (% n 3)) nil)
(t (let ((bound (floor (sqrt n))))
(named-let f ((i 5))
(cond
((> i bound) t)
((zerop (% n i)) nil)
((zerop (% n (+ i 2))) nil)
(t (f (+ i 6)))))))))
(named-let f ((n 3) (sum 2))
(cond
((>= n 2000000) sum)
(t (if (eu7-isprime n)
(f (+ n 2) (+ sum n))
(f (+ n 2) sum)))))
;; 142913828922
对于这个问题来说上面的代码是够用的,但是整个过程的复杂度大概是 O(n1.5) (isprime 函数的复杂度大概是 O(n0.5))。下面我们用埃氏筛实现一下,它的复杂度是 O(nlog(n)log(n)),整个算法的步骤大概是这样:
- Make a list of all numbers from 2 to N.
- Find the next number p not yet crossed out. This is a prime. If it is greater than √N, go to 5.
- Cross out all multiples of p which are not yet crossed out.
- Go to 2.
- The numbers not crossed out are the primes not exceeding N.
(defun eu10-sieve-of-Era (n)
(let ((limit (floor (sqrt n)))
(vec (make-bool-vector (1+ n) t)))
(aset vec 0 nil)
(aset vec 1 nil)
(cl-loop for i from 4 to n by 2
do (aset vec i nil))
(cl-loop for i from 3 to limit by 2
do (when (aref vec i)
(cl-loop for m from (* i i) to n by (* i 2)
do (aset vec m nil))))
vec))
(cl-loop for a across (eu10-sieve-of-Era 2000000)
for i from 0
sum (if a i 0))
;; 142913828922
由于除了 2 以外的所有偶数都不可能是素数,我们完全可以忽略它们而只处理奇数,现在我们建立如下索引的数组:
0, 1, 2, 3, 4,…
1, 3, 5, 7, 9,…
将上面的数字乘二加一,我们就可以得到所有的奇数了。对于给定的范围 N,我们需要的数组大小就是 (N+1)/2。比如对于 1000 或 999,我们需要的奇数就是 500 个(当然如果我们忽略掉 1 的话,那我们就只需要 (N-1)/2 个了,为了让索引与自然数对应,这里我们还是取 (N+1)/2,然后把 1 留个 0)。
现在让我们来考虑索引问题,现在 1 对应于 3,2 对应于 5,假设我们碰到了某个素数,我们要使用它筛掉它的倍数,那么步进值应该取多少?首先假设这个索引是 i,那么对应的数字就是 2×i+1,(2*i+1)2=4×i2+4×i+1,将这个减一除二就可以得到它在数组中的索引:2(i2+i)。在上面的代码中步进值是 2×i,那么这里应该就是 i(全是奇数,不用跳过偶数了),然后替换为 2×i+1,我们就得到了步进值。下面是实现代码:
(defun eu10-sieve-of-Era2 (n)
(let* ((bound (/ (1+ n) 2))
(vec (make-bool-vector bound t))
(crosslimit (/ (floor (sqrt n)) 2)))
(aset vec 0 nil)
(cl-loop for i from 1 to crosslimit
do (when (aref vec i)
(cl-loop for j from (* 2 i (1+ i)) to (1- bound) by (1+ (* i 2))
do (aset vec j nil))))
vec))
(cl-loop for a across (eu10-sieve-of-Era2 2000000)
for i from 1
sum (if a (1+ (* i 2)) 0))
理论上这能快一倍,不过实际可能要慢一会儿。