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

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

有一个100%的数学测试可以检查一个数字P是质数还是合数，叫做AKS质数测试。

概念很简单:给定一个数字P，如果(x-1)^P - (x^P-1)的所有系数都能被P整除，那么P是一个质数，否则它是一个合数。

例如，给定P = 3，会给出多项式:

   (x-1)^3 - (x^3 - 1)
 = x^3 + 3x^2 - 3x - 1 - (x^3 - 1)
 = 3x^2 - 3x

系数都能被3整除，所以这个数是素数。

P = 4不是质数的例子是:

   (x-1)^4 - (x^4-1)
 = x^4 - 4x^3 + 6x^2 - 4x + 1 - (x^4 - 1)
 = -4x^3 + 6x^2 - 4x

这里我们可以看到系数6不能被4整除，因此它不是质数。

多项式(x-1)^P有P+1项，可以用组合法找到。因此，这个测试将在O(n)个运行时间内运行，所以我不知道这有多有用，因为你可以简单地从0到p遍历I，然后测试剩余的部分。

这是我一直在玩的埃拉托色尼筛子的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个数字。

欢迎提出建议!

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.

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

到目前为止，我认为最快的质数测试算法是强或然质数(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