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

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

一种聪明而有效的方法是预先计算质数表，并使用位级编码将它们保存在文件中。文件被认为是一个长位向量，而位n表示整数n。如果n是素数，则其位设置为1，否则为0。查找非常快(您可以计算字节偏移量和位掩码)，并且不需要在内存中加载文件。

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

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

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

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