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


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

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

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

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

非常感谢!


29
2017-10-09 18:01


起源


Project Euler的目的是让你锻炼你的数学和编程能力,并继续研究和改进它们。 “仅仅死亡率”不是借口 - Project Euler旨在帮助您克服这一限制! - yfeldblum
地狱我甚至知道有些神仙在某些问题上黯然失色。这是砍掉头脑吃掉灵魂的最佳时机。 - Josh


答案:


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

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

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

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


28
2017-10-09 18:05



该死。你打败了我。 - Herms
你的答案中有一个错字,他的名字通常写着:“Eratosthenes” - Stephen Denne


生成小于限制的所有素数 Eratosthenes的筛子 (该页面包含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]

17
2017-10-11 02:13



很干净。 :-D很好。 - J.J.
OP说 not confuse a mere mortal programmer?。这个 stackoverflow.com/questions/231767/... 让我思考 yield 令人困惑.. - Koray Tugay


我看到Fermat的素性测试已被提出,但我一直在努力 计算机程序的结构与解释,他们也给了 米勒 - 拉宾测试 (参见第1.2.6节,问题1.28)作为另一种选择。我一直在使用它成功地解决欧拉问题。


11
2017-10-09 20:17



我也使用Miller-Rabin来解决一些问题+1 - rslite
但我怀疑它比问题中提出的算法更快?你使用随机版吗? - vahidg
费马的测试与卡迈克尔的数字存在问题。 - Jason S


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


5
2017-10-09 18:25



有一个更简单的选项:从5开始,增加2和4.效果是相同的,即 - 基于(2,3)的车轮优化。看到 stackoverflow.com/questions/188425/project-euler-problem#193589 - jfs


牢记以下事实(来自 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)
}

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


5
2018-01-25 22:50





我推荐 费马的素性测试。这是一个概率测试,但它经常出人意料地正确。与筛子相比,它的速度非常快。


3
2017-10-09 18:22



差不多+1。问题是费马的测试对卡迈克尔的数字失败了。 - Jason S
Miller-Rabin测试只是稍微困难一些,在维基百科上,您会发现非常快速的变体可以确定地用于所有32位数,或者n <3 * 10 ^ 18。先用几个小素数来检查除法。 - gnasher729


对于相当小的数字,高达sqrt(x)的x%n非常快速且易于编码。

简单的改进:

仅测试2和奇数。

测试2,3和6 +或-1的倍数(除了2或3之外的所有素数都是6 +/- 1的倍数,所以你基本上只是跳过所有偶数和所有3的倍数

仅测试素数(需要计算或存储所有素数,最大为sqrt(x))

您可以使用筛选方法快速生成所有素数列表,直到任意限制,但它往往是内存密集型。您可以使用6技巧的倍数将内存使用量降低到每个数字的1/3。

我写了一个简单的素数类(C#),它使用两个位域为6 + 1的倍数和6-1的倍数,然后进行简单的查找......如果我测试的数字超出了筛子的范围,然后它再次回到测试2,3和6 +/- 1的倍数。我发现生成一个大筛子实际上需要花费更多的时间来计算到目前为止我解决的大部分欧拉问题。 KISS原则再次出现!

我写了一个使用筛子预先计算较小质数的素数类,然后依靠测试2,3和6 +/- 1的倍数用于筛子范围之外的那些。


2
2017-12-01 04:36





对于Project Euler来说,拥有素数列表非常重要。我建议维护一个用于每个问题的列表。

我想你要找的是 Eratosthenes的筛子


1
2017-10-09 18:10