我最近写了这段代码来求数字的和。它可以很容易地修改，以确定一个数字是否是质数。基准测试在代码之上。

// built on core-i2 e8400
// Benchmark from PowerShell
// Measure-Command { ExeName.exe }
// Days              : 0
// Hours             : 0
// Minutes           : 0
// Seconds           : 23
// Milliseconds      : 516
// Ticks             : 235162598
// TotalDays         : 0.00027217893287037
// TotalHours        : 0.00653229438888889
// TotalMinutes      : 0.391937663333333
// TotalSeconds      : 23.5162598
// TotalMilliseconds : 23516.2598
// built with latest MSVC
// cl /EHsc /std:c++latest main.cpp /O2 /fp:fast /Qpar

#include <cmath>
#include <iostream>
#include <vector>

inline auto prime = [](std::uint64_t I, std::vector<std::uint64_t> &cache) -> std::uint64_t {
    std::uint64_t root{static_cast<std::uint64_t>(std::sqrtl(I))};
    for (std::size_t i{}; cache[i] <= root; ++i)
        if (I % cache[i] == 0)
            return 0;

    cache.push_back(I);
    return I;
};

inline auto prime_sum = [](std::uint64_t S) -> std::uint64_t {
    std::uint64_t R{5};
    std::vector<std::uint64_t> cache;
    cache.reserve(S / 16);
    cache.push_back(3);

    for (std::uint64_t I{5}; I <= S; I += 8)
    {
        std::uint64_t U{I % 3};
        if (U != 0)
            R += prime(I, cache);
        if (U != 1)
            R += prime(I + 2, cache);
        if (U != 2)
            R += prime(I + 4, cache);
        R += prime(I + 6, cache);
    }
    return R;
};

int main()
{
    std::cout << prime_sum(63210123);
}

一个非常快速的Atkin Sieve的实现是Dan Bernstein的primegen。这个筛子比埃拉托色尼的筛子更有效率。他的页面有一些基准测试信息。

I know it's somewhat later, but this could be useful to people arriving here from searches. Anyway, here's some JavaScript that relies on the fact that only prime factors need to be tested, so the earlier primes generated by the code are re-used as test factors for later ones. Of course, all even and mod 5 values are filtered out first. The result will be in the array P, and this code can crunch 10 million primes in under 1.5 seconds on an i7 PC (or 100 million in about 20). Rewritten in C it should be very fast.

var P = [1, 2], j, k, l = 3

for (k = 3 ; k < 10000000 ; k += 2)
{
  loop: if (++l < 5)
  {
    for (j = 2 ; P[j] <= Math.sqrt(k) ; ++j)
      if (k % P[j] == 0) break loop

    P[P.length] = k
  }
  else l = 0
}

我总是用这种方法来计算筛子算法后面的质数。

void primelist()
 {
   for(int i = 4; i < pr; i += 2) mark[ i ] = false;
   for(int i = 3; i < pr; i += 2) mark[ i ] = true; mark[ 2 ] = true;
   for(int i = 3, sq = sqrt( pr ); i < sq; i += 2)
       if(mark[ i ])
          for(int j = i << 1; j < pr; j += i) mark[ j ] = false;
  prime[ 0 ] = 2; ind = 1;
  for(int i = 3; i < pr; i += 2)
    if(mark[ i ]) ind++; printf("%d\n", ind);
 }

我最近写了这段代码来求数字的和。它可以很容易地修改，以确定一个数字是否是质数。基准测试在代码之上。

// built on core-i2 e8400
// Benchmark from PowerShell
// Measure-Command { ExeName.exe }
// Days              : 0
// Hours             : 0
// Minutes           : 0
// Seconds           : 23
// Milliseconds      : 516
// Ticks             : 235162598
// TotalDays         : 0.00027217893287037
// TotalHours        : 0.00653229438888889
// TotalMinutes      : 0.391937663333333
// TotalSeconds      : 23.5162598
// TotalMilliseconds : 23516.2598
// built with latest MSVC
// cl /EHsc /std:c++latest main.cpp /O2 /fp:fast /Qpar

#include <cmath>
#include <iostream>
#include <vector>

inline auto prime = [](std::uint64_t I, std::vector<std::uint64_t> &cache) -> std::uint64_t {
    std::uint64_t root{static_cast<std::uint64_t>(std::sqrtl(I))};
    for (std::size_t i{}; cache[i] <= root; ++i)
        if (I % cache[i] == 0)
            return 0;

    cache.push_back(I);
    return I;
};

inline auto prime_sum = [](std::uint64_t S) -> std::uint64_t {
    std::uint64_t R{5};
    std::vector<std::uint64_t> cache;
    cache.reserve(S / 16);
    cache.push_back(3);

    for (std::uint64_t I{5}; I <= S; I += 8)
    {
        std::uint64_t U{I % 3};
        if (U != 0)
            R += prime(I, cache);
        if (U != 1)
            R += prime(I + 2, cache);
        if (U != 2)
            R += prime(I + 4, cache);
        R += prime(I + 6, cache);
    }
    return R;
};

int main()
{
    std::cout << prime_sum(63210123);
}

这是我一直在玩的埃拉托色尼筛子的Python实现。

def eratosthenes(maximum: int) -> list[int | None]:
    """
    Find all the prime numbers between 2 and `maximum`.

    Args:
        maximum: The maximum number to check.

    Returns:
        A list of primes between 2 and `maximum`.
    """

    if maximum < 2:
        return []

    # Discard even numbers by default.
    sequence = dict.fromkeys(range(3, maximum+1, 2), True)

    for num, is_prime in sequence.items():
        # Already filtered, let's skip it.
        if not is_prime:
            continue

        # Avoid marking the same number twice.
        for num2 in range(num ** 2, maximum+1, num):
            # Here, `num2` might contain an even number - skip it.
            if num2 in sequence:
                sequence[num2] = False

    # Re-add 2 as prime and filter out the composite numbers.
    return [2] + [num for num, is_prime in sequence.items() if is_prime]

在一台简陋的三星Galaxy A40上，该代码大约需要16秒才能输入10000000个数字。

欢迎提出建议!