I found this solution pretty fast but it comes with consequences, So this is called Fermat's Little Theorem. If we take any number p and put that in (1^p)-1 or (2^p)-2...(n^p)-n likewise and the number we get is divisible by p then it's a prime number. Talking about consequences, it's not 100% right solution. There are some numbers like 341(not prime) it will pass the test with (2^341)-2 but fails on (3^341)-3, so it's called a composite number. We can have two or more checks to make sure they pass all of them. There is one more kind of number which are not prime but also pass all the test case:( 561, 1729 Ramanujan taxi no etc.

好消息是:在前250亿个数字中，只有2183不符合这个要求 的情况。

#include <iostream>
#include <math.h>
using namespace std;

int isPrime(int p)
{
    int tc = pow(2, p) - 2;
    if (tc % p == 0)
    {
        cout << p << "is Prime ";
    }
    else
    {
        cout << p << "is Not Prime";
    }
    return 0;
}

int main()
{
    int p;
    cin >> p;
    isPrime(p);
    return 0;
} 

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

另一个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，或者硬编码更多质数，但我想保持简单。

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

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

i wrote it today in C,compiled with tcc, figured out during preparation of compititive exams several years back. don't know if anyone already have wrote it alredy. it really fast(but you should decide whether it is fast or not). took one or two minuts to findout about 1,00,004 prime numbers between 10 and 1,00,00,000 on i7 processor with average 32% CPU use. as you know, only those can be prime which have last digit either 1,3,7 or 9 and to check if that number is prime or not, you have to divide that number by previously found prime numbers only. so first take group of four number = {1,3,7,9}, test it by dividing by known prime numbers, if reminder is non zero then number is prime, add it to prime number array. then add 10 to group so it becomes {11,13,17,19} and repeat the process.

#include <stdio.h>
int main() {    
    int nums[4]={1,3,7,9};
    int primes[100000];
    primes[0]=2;
    primes[1]=3;
    primes[2]=5;
    primes[3]=7;
    int found = 4;
    int got = 1;
    int m=0;
    int upto = 1000000;
    for(int i=0;i<upto;i++){
        //printf("iteration number: %d\n",i);
        for(int j=0;j<4;j++){
            m = nums[j]+10;
            //printf("m = %d\n",m);
            nums[j] = m;
            got = 1;
            for(int k=0;k<found;k++){
                //printf("testing with %d\n",primes[k]);
                if(m%primes[k]==0){
                    got = 0;
                    //printf("%d failed for %d\n",m,primes[k]);
                    break;
                }
            }
            if(got==1){
                //printf("got new prime: %d\n",m);
                primes[found]= m;
                found++;
            }
        }
    }
    printf("found total %d prime numbers between 1 and %d",found,upto*10);
    return 0;
}

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

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