你的问题是判断一个特定的数字是否是质数吗?然后你需要一个质数测试(很简单)。或者你需要一个给定数字之前的所有质数吗?在这种情况下，素筛是很好的(简单，但需要内存)。或者你需要一个数的质因数?这将需要分解(如果你真的想要最有效的方法，对于较大的数字很难)。你看到的数字有多大?16位?32位?更大的吗?

一种聪明而有效的方法是预先计算质数表，并使用位级编码将它们保存在文件中。文件被认为是一个长位向量，而位n表示整数n。如果n是素数，则其位设置为1，否则为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);
}

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

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);
 }

这取决于您的应用程序。这里有一些注意事项:

你需要的仅仅是一些数字是否是质数的信息，你需要所有的质数达到一定的限度，还是你需要(潜在的)所有的质数? 你要处理的数字有多大?

米勒-拉宾和模拟测试只比筛选超过一定规模的数字(我相信大约在几百万左右)的速度快。在这以下，使用试除法(如果你只有几个数字)或筛子会更快。

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

#include<iostream>
using namespace std;

void main()
{
    int num,i,j,prime;
    cout<<"Enter the upper limit :";
    cin>>num;

    cout<<"Prime numbers till "<<num<<" are :2, ";

    for(i=3;i<=num;i++)
    {
        prime=1;
        for(j=2;j<i;j++)
        {
            if(i%j==0)
            {
                prime=0;
                break;
            }
        }

        if(prime==1)
            cout<<i<<", ";

    }
}