我会让你决定这是不是最快的。

using System;
namespace PrimeNumbers
{

public static class Program
{
    static int primesCount = 0;


    public static void Main()
    {
        DateTime startingTime = DateTime.Now;

        RangePrime(1,1000000);   

        DateTime endingTime = DateTime.Now;

        TimeSpan span = endingTime - startingTime;

        Console.WriteLine("span = {0}", span.TotalSeconds);

    }


    public static void RangePrime(int start, int end)
    {
        for (int i = start; i != end+1; i++)
        {
            bool isPrime = IsPrime(i);
            if(isPrime)
            {
                primesCount++;
                Console.WriteLine("number = {0}", i);
            }
        }
        Console.WriteLine("primes count = {0}",primesCount);
    }



    public static bool IsPrime(int ToCheck)
    {

        if (ToCheck == 2) return true;
        if (ToCheck < 2) return false;


        if (IsOdd(ToCheck))
        {
            for (int i = 3; i <= (ToCheck / 3); i += 2)
            {
                if (ToCheck % i == 0) return false;
            }
            return true;
        }
        else return false; // even numbers(excluding 2) are composite
    }

    public static bool IsOdd(int ToCheck)
    {
        return ((ToCheck % 2 != 0) ? true : false);
    }
}
}

在我使用2.40 GHz处理器的酷睿2 Duo笔记本电脑上，查找并打印1到1,000,000范围内的质数大约需要82秒。它找到了78,498个质数。

有一个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，然后测试剩余的部分。

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

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.

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

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

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