问题
小于10的素数的和是：2 + 3 + 5 + 7 = 17。
那么小于200万的素数和是多少？
* 传送门
分析
又是素数！?只能简单粗暴。
答案
// answer1: brute force
const start = Date.now()
function isPrime(n) {
if (n == 2 || n == 3 || n == 5 || n == 7)
return true
else if (n < 2)
return false
if ((n % 2) == 0)
return false
const end = Math.sqrt(n)
for (let i = 3; i <= end; i += 2)
if ((n % i) == 0)
return false
return true
}
function* primes() {
yield 2
for (let odd = 3; true; odd += 2)
if (isPrime(odd))
yield odd
}
var sum = 0
for (const prime of primes())
if (prime < 2000000) sum += prime
else break
alert(sum + ', ' + (Date.now() - start) + 'ms')
还可以使用筛的方法，除去数组中下标为合数的所有数，剩下的便是素数，复杂度\(O(n\log \log n)\)会比直接暴力计算\(O(n^2)\)低：
// answer2: using eratosthenes sieve
const start = Date.now()
function* primesBelow(n) {
const sieve = new BitSet // https://github.com/infusion/BitSet.js
sieve.flip(0, n)
.set(0, 0)
.set(1, 0)
for (let i = 2; i < n; ++i) {
if (sieve.get(i) == 0)
continue
for (let j = 2 * i; j < n; j += i)
sieve.set(j, 0)
}
for (let i = 2; i < n; ++i)
if (sieve.get(i) == 1)
yield i
}
var sum = 0
for (const prime of primesBelow(2000000))
sum += prime
alert(sum + ', ' + (Date.now() - start) + 'ms')
