Rabin-Miller是一个标准的概率质数检验。(你运行K次，输入数字要么肯定是合数，要么可能是素数，误差概率为4-K。(经过几百次迭代，它几乎肯定会告诉你真相)

拉宾·米勒有一个非概率(确定性)的变体。

The Great Internet Mersenne Prime Search (GIMPS) which has found the world's record for largest proven prime (274,207,281 - 1 as of June 2017), uses several algorithms, but these are primes in special forms. However the GIMPS page above does include some general deterministic primality tests. They appear to indicate that which algorithm is "fastest" depends upon the size of the number to be tested. If your number fits in 64 bits then you probably shouldn't use a method intended to work on primes of several million digits.

#include <iostream>

using namespace std;

int set [1000000];

int main (){

    for (int i=0; i<1000000; i++){
        set [i] = 0;
    }
    int set_size= 1000;
    set [set_size];
    set [0] = 2;
    set [1] = 3;
    int Ps = 0;
    int last = 2;

    cout << 2 << " " << 3 << " ";

    for (int n=1; n<10000; n++){
        int t = 0;
        Ps = (n%2)+1+(3*n);
        for (int i=0; i==i; i++){
            if (set [i] == 0) break;
            if (Ps%set[i]==0){
                t=1;
                break;
            }
        }
        if (t==0){
            cout << Ps << " ";
            set [last] = Ps;
            last++;
        }
    }
    //cout << last << endl;


    cout << endl;

    system ("pause");
    return 0;
}

#include<stdio.h>
main()
{
    long long unsigned x,y,b,z,e,r,c;
    scanf("%llu",&x);
    if(x<2)return 0;
    scanf("%llu",&y);
    if(y<x)return 0;
    if(x==2)printf("|2");
    if(x%2==0)x+=1;
    if(y%2==0)y-=1;
    for(b=x;b<=y;b+=2)
    {
        z=b;e=0;
        for(c=2;c*c<=z;c++)
        {
            if(z%c==0)e++;
            if(e>0)z=3;
        }
        if(e==0)
        {
            printf("|%llu",z);
            r+=1;
        }
    }
    printf("|\n%llu outputs...\n",r);
    scanf("%llu",&r);
}    

另一个Python实现比死亡面具推销员的答案更直接，也更快:

import numpy as np

def prime_numbers(limit: int) -> list[int]:
    """Provide a list of all prime numbers <= the limit."""
    is_prime = np.full((limit + 1, ), True)
    is_prime[0:2] = False
    for n in range(2, limit + 1):
        if is_prime[n]:
            is_prime[n**2::n] = False
    return list(np.where(is_prime)[0])

你可以进一步优化，例如，排除2，或者硬编码更多质数，但我想保持简单。

*示例运行时比较(注意:我使用了其他实现的优化形式，见我的评论):

这是找到从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/

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