什么是更好的方法来检查一个数字是否为总数？

可能重复：
Checking if an int is prime more efficiently 什么是更好的方法来检查一个数字是否为总数？

bool isPrime(int num) 
{ 
    for(int i = 2; i <= (num/2)+1; i++) 
    { 
     if(num % i == 0) 
     { 
      return false; 
     } 
    } 
    return true; 
}

我看维基百科上，但我不明白任何它所描述的快速素性测试。

来源

2011-07-18 Avery3R

除了在你的算法下文所述的简单的错误，“精益求精”的方式要复杂得多。数百年来，数学家一直在研究素数。 –

@Kirill：在标记为复制之前阅读另一个问题，该问题是关于找到具有某些特征的素数（即许多数字必须经过测试）。我确实相信这个问题以前曾被问过，但事实并非如此。 –

首先，你只需要迭代，而i * i <= num。

之后，您可能会注意到测试数字是否为2的倍数仅仅是一个测试。一旦你知道这个数字不是偶数，你就知道没有偶数因素，所以你可以跳过测试它们。

这导致：

bool isPrime(int num) 
{ 
    if (num < 4) return true; 
    if (~num & 1) return false; 
    for(int i = 3; i * i <= num; i += 2) 
    { 
     if (num % i == 0) return false; 
    } 
    return true; 
}

来源

2011-07-18 04:11:47

你确定'if（〜num＆1）return false;' –

@Martin：很确定。即使不少于四个数字也不是素数。你有没有失败的情况？ –

也许你应该加上'if（num <1）返回false;'因为IIRC，素数在定义上大于1. –

更好的方式（如果你想加快你的应用程序）是预先计算的第一个素数，将它们添加到数组，只是搜索你的号码中，或者检查数组元素的划分。

你也可以检查num % i == 0不高达num/2，但高达sqrt(num)。

PS：

if(num % i == 0) 
     { 
      return true; 
     }

您必须返回false :)

来源

2011-07-18 04:13:01 Olympian

对于不是你的方法更快的东西，你应该建立使用的埃拉托色尼筛等（生成素数至少就一个素数表作为你测试的数字）。然后只需使用二进制搜索来查看您的号码。如果你保留表格，如果你以后需要查找更高的数字，你可以逐渐增加它。

Gogo动态规划。 :-)

来源

2011-07-18 04:14:07

没有什么事情可以做，以加快这：

，而不是从2日开始，做i++的，检查它是否甚至在第一次开始的，如果不是，就在第3和增量I由两个：

if (num % 2 == 0) { 
    return false; 
} 
for (int i = 3; i <= sqrt(num); i += 2) { ... }

在该示例中的另一个端头已经是设置上限到你的电话号码，而不是num/2的平方根。

还有一件事情需要一点点设置，就是使用prime sieve来快速测试您的号码是否为总数。

来源

2011-07-18 04:18:14

我不建议每次迭代都进行'i <= sqrt（num）'测试。相反，将'sqrt（num）'存储在类型为'int'（或'long'，或另一个整型）的变量中，并与每次迭代进行比较。 –

如果你的输入集特别小，那么你可以在你使用sieve of erathones构建素数然后在该筛上进行素性测试的时候有一个步骤。这是你的算法之后的下一步。

有许多性能调整，你可以更快的素性测试，如跳过2和3的因素等

来源

2011-07-18 04:19:21

米勒 - 拉宾测试实现起来比较简单，虽然证明这是正确得多难。基本上，你多次运行这个测试;每次你从2到你的号码之间选择一个随机的“见证”号码，然后运行算法。测试会告诉你，你的号码肯定是复合的（不是总数），也可能是总数（每次出现错误的概率为1/4），所以如果你用10个随机证人跑10次测试并得到“可能是最好的“，每次的机会都小于百万分之一，这个数字实际上是复合数。

维基百科在伪代码的实现：http://en.wikipedia.org/wiki/Miller-Rabin_test#Algorithm_and_running_time

来源

2011-07-18 04:35:39 duskwuff

什么是更好的方法来检查一个数字是否为总数？

回答

相关问题