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
}

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

// 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。这个筛子比埃拉托色尼的筛子更有效率。他的页面有一些基准测试信息。

这是找到从1到n的所有质数的最快算法(在我的电脑上，它只花了0.004秒就找到了从1到1000000的所有质数)。

#include <iostream>
#include <fstream>

using namespace std;

double FindPrime(bool* array, int size){
clock_t start;
double runtime;
for (int i = 2; i < size; i++)
    array[i] = true;
start = clock();
for (int i = 2; i <= size; i++)
    if (array[i])
        for (int j = 2 * i; j < size; j += i)
            array[j] = false;
runtime = (double)(clock() - start) / CLOCKS_PER_SEC;
return runtime;
}


int main() {
ofstream fout("prime.txt");
int n = 0;
cout << "Enter the upper limit of prime numbers searching algorithm:";
cin >> n;
bool* array = new bool[n + 1];
double duration = FindPrime(array, n + 1);
printf("\n%f seconds.\n", duration);
for (int i = 2; i <= n; i++)
    if (array[i])
        fout << i << endl;
fout.close();

return 0;
}

如果它必须非常快，你可以包括一个质数列表: http://www.bigprimes.net/archive/prime/

如果你只想知道某个数是不是质数，维基百科上列出了各种质数判别法。它们可能是确定大数是否为质数的最快方法，特别是因为它们可以告诉你一个数是否为质数。

他，他我知道我是一个回答老问题的问题巫师，但我只是在网上搜索实现有效质数测试的方法时发现了这个问题。

到目前为止，我认为最快的质数测试算法是强或然质数(SPRP)。我引用Nvidia CUDA论坛:

One of the more practical niche problems in number theory has to do with identification of prime numbers. Given N, how can you efficiently determine if it is prime or not? This is not just a thoeretical problem, it may be a real one needed in code, perhaps when you need to dynamically find a prime hash table size within certain ranges. If N is something on the order of 2^30, do you really want to do 30000 division tests to search for any factors? Obviously not. The common practical solution to this problem is a simple test called an Euler probable prime test, and a more powerful generalization called a Strong Probable Prime (SPRP). This is a test that for an integer N can probabilistically classify it as prime or not, and repeated tests can increase the correctness probability. The slow part of the test itself mostly involves computing a value similar to A^(N-1) modulo N. Anyone implementing RSA public-key encryption variants has used this algorithm. It's useful both for huge integers (like 512 bits) as well as normal 32 or 64 bit ints. The test can be changed from a probabilistic rejection into a definitive proof of primality by precomputing certain test input parameters which are known to always succeed for ranges of N. Unfortunately the discovery of these "best known tests" is effectively a search of a huge (in fact infinite) domain. In 1980, a first list of useful tests was created by Carl Pomerance (famous for being the one to factor RSA-129 with his Quadratic Seive algorithm.) Later Jaeschke improved the results significantly in 1993. In 2004, Zhang and Tang improved the theory and limits of the search domain. Greathouse and Livingstone have released the most modern results until now on the web, at http://math.crg4.com/primes.html, the best results of a huge search domain.

更多信息请看这里: http://primes.utm.edu/prove/prove2_3.html和http://forums.nvidia.com/index.php?showtopic=70483

如果您只是需要一种方法来生成非常大的质数，而不关心生成所有<整数n的质数，您可以使用Lucas-Lehmer检验来验证梅森质数。梅森质数的形式是2^p -1。我认为卢卡斯-莱默检验是目前发现的梅森质数最快的算法。

如果你不仅想使用最快的算法，而且还想使用最快的硬件，那就尝试使用Nvidia CUDA来实现它，为CUDA写一个内核，然后在GPU上运行。

如果你发现足够大的质数，你甚至可以赚到一些钱，EFF提供的奖金从5万美元到25万美元不等: https://www.eff.org/awards/coop