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

欢迎提出建议!

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

欢迎提出建议!

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

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

这取决于您的应用程序。这里有一些注意事项:

你需要的仅仅是一些数字是否是质数的信息，你需要所有的质数达到一定的限度，还是你需要(潜在的)所有的质数? 你要处理的数字有多大?

米勒-拉宾和模拟测试只比筛选超过一定规模的数字(我相信大约在几百万左右)的速度快。在这以下，使用试除法(如果你只有几个数字)或筛子会更快。

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

我总是用这种方法来计算筛子算法后面的质数。

void primelist()
 {
   for(int i = 4; i < pr; i += 2) mark[ i ] = false;
   for(int i = 3; i < pr; i += 2) mark[ i ] = true; mark[ 2 ] = true;
   for(int i = 3, sq = sqrt( pr ); i < sq; i += 2)
       if(mark[ i ])
          for(int j = i << 1; j < pr; j += i) mark[ j ] = false;
  prime[ 0 ] = 2; ind = 1;
  for(int i = 3; i < pr; i += 2)
    if(mark[ i ]) ind++; printf("%d\n", ind);
 }