是否有一个简单的算法可以确定X是否是素数,而不是混淆一个凡人的程序员?

Pulsehead 29 algorithm primes

我一直试图通过Project Euler工作,并注意到一些问题要求你确定一个素数作为其中的一部分.

  1. 我知道我可以将x除以2,3,4,5,...,X的平方根,如果我到达平方根,我可以(安全地)假设该数字是素数.不幸的是,这个解决方案似乎非常笨重.

  2. 我已经研究了如何确定数字是否为素数的更好的算法,但是快速混淆.

是否有一个简单的算法可以确定X是否是素数,而不是混淆一个凡人的程序员?

非常感谢!

rslite.. 28

第一个算法非常好,并且在Project Euler上使用了很多.如果你知道你想要的最大数量,你也可以研究Eratosthenes的筛子.

如果你保持素数列表,你也可以改进第一个算法,只用素数除以数字的平方根.

有了这两个算法(划分和筛子),你应该能够解决问题.

编辑:注释中注明的固定名称


jfs.. 19

要生成小于限制的所有素数,Eratosthenes的Sieve(该页面包含20种编程语言的变体)是最古老和最简单的解决方案.

在Python中:

def iprimes_upto(limit):
    is_prime = [True] * limit
    for n in range(2, limit):
        if is_prime[n]:
           yield n
           for i in range(n*n, limit, n): # start at ``n`` squared
               is_prime[i] = False

例:

>>> list(iprimes_upto(15))
[2, 3, 5, 7, 11, 13]


Tim Whitcomb.. 11

我看到Fermat的素性测试已经被提出了,但我一直在研究计算机程序的结构和解释,他们也将Miller-Rabin测试(参见第1.2.6节,问题1.28)作为另一种选择.我一直在使用它成功解决欧拉问题.


Jouni K. Sep.. 5

这是一个简单的方法优化,它不是Eratosthenes的Sieve,但很容易实现:首先尝试将X除以2和3,然后循环j = 1..sqrt(X)/ 6,试图划分乘以6*j-1和6*j + 1.这会自动跳过可被2或3整除的所有数字,从而获得非常好的常数因子加速度.


Bill the Liz.. 5

请记住以下事实(来自MathsChallenge.net):

  • 除2之外的所有素数都是奇数.
  • 所有大于3的素数都可以用6k - 1或6k + 1的形式写出.
  • 你不需要检查n的平方根

这是我用于相对较小的n的C++函数:

bool isPrime(unsigned long n)
{
    if (n == 1) return false; // 1 is not prime
    if (n < 4) return true; // 2 and 3 are both prime
    if ((n % 2) == 0) return false; // exclude even numbers
    if (n < 9) return true; //we have already excluded 4, 6, and 8.
    if ((n % 3) == 0) return false; // exclude remaining multiples of 3

    unsigned long r = floor( sqrt(n) );
    unsigned long f = 5;
    while (f <= r)
    {
        if ((n % f) == 0)  return false;
        if ((n % (f + 2)) == 0) return false;
        f = f + 6;
    }
    return true; // (in all other cases)
}

您可能会想到自己的更多优化.