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

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

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

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

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

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

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实现。

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个数字。

欢迎提出建议!

I know it's somewhat later, but this could be useful to people arriving here from searches. Anyway, here's some JavaScript that relies on the fact that only prime factors need to be tested, so the earlier primes generated by the code are re-used as test factors for later ones. Of course, all even and mod 5 values are filtered out first. The result will be in the array P, and this code can crunch 10 million primes in under 1.5 seconds on an i7 PC (or 100 million in about 20). Rewritten in C it should be very fast.

var P = [1, 2], j, k, l = 3

for (k = 3 ; k < 10000000 ; k += 2)
{
  loop: if (++l < 5)
  {
    for (j = 2 ; P[j] <= Math.sqrt(k) ; ++j)
      if (k % P[j] == 0) break loop

    P[P.length] = k
  }
  else l = 0
}