问题

小于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')

求值

bruce天地不仁，以万物为刍狗

微信支付

支付宝

PayPal链接

https://paypal.me/xieweiking

由 bruce 于 2020-06-8 19:28 更新