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

发布于 2024-11-24 08:19:11 字数 420 浏览 0 评论 0原文

可能的重复：
更有效地检查 int 是否为素数

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

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

原文

Possible Duplicate:
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;
}

I've looked on Wikipedia, but I don't understand any of the fast primality tests it describes.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

伪装你 2024-12-01 08:19:11

一方面，您只需要在 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;
}

For one thing, you only need to iterate while i * i <= num.

After that, you might notice that testing whether a number is a multiple of 2 is just a bit test. Once you know the number isn't even, you know there are no even factors, so you can skip testing them.

That leads to:

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

回复收藏 0 原文

望喜 2024-12-01 08:19:11

如果您的输入集特别小，那么您可以使用erathones 筛构建素数的步骤< /a> 然后对该筛子进行素性测试。这是算法之后的下一步。

您可以进行许多性能调整以加快素数测试速度，例如跳过 2 和 3 的因子等。

回复收藏 0 原文

想念有你 2024-12-01 08:19:11

更好的方法（如果您想加快应用程序的速度）是首先预先计算素数，将它们添加到数组中，然后在其中搜索您的数字，或者检查数组元素的除法。

您还可以检查 num % i == 0 不超过 num/2，但不超过 sqrt(num)。

PS:

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

必须返回 false:)

The better way(if you want speed up your application) is pre-calculate at first prime numbers, add them into array and just search your number in it, or check division on array elements.

Also you can check num % i == 0 not upto num/2, but up to sqrt(num).

PS:

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

You must return false:)

回复收藏 0 原文

夏了南城 2024-12-01 08:19:11

对于比您的方法更快的方法，您应该使用埃拉托色尼筛法或类似方法构建一个素数表（至少生成与您正在测试的数字相同的素数）。然后只需使用二分搜索查找您的号码即可。如果保留该表，如果以后需要查找更高的数字，则可以逐步建立它。

Gogo动态规划。 :-)

回复收藏 0 原文

小霸王臭丫头 2024-12-01 08:19:11

您可以采取一些措施来加快速度：

不要从 2 开始执行 i++，而是首先检查它是否在开头，如果不是，则从 3 开始并将 i 增加 2

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

：本示例中的提示是将上限设置为数字的平方根，而不是 num/2。

另一件需要一点设置的事情是使用 prime sieve 来快速测试您的数是素数。

Few things you can do to speed this up:

Instead of starting from 2 and doing i++, check if it's even in the beginning first, and if it's not, start at 3 and increment i by two:

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

Another tip already in this example is to set your upper bound to the square root of your number instead of num/2.

One more thing that requires a little bit of setup is to employ a prime sieve to quickly test if your number is prime.

回复收藏 0 原文

心作怪 2024-12-01 08:19:11

米勒-拉宾检验实施起来相对简单，但证明其正确性要困难得多。基本上，您需要多次运行此测试；每次，您在 2 和您的数字之间选择一个随机“见证”数字，然后运行算法。测试将告诉您，您的数字肯定是合数（不是素数），或者它可能是素数（每次都错的概率为 1/4），因此，如果您使用 10 个随机见证人运行测试 10 次，并得到“每次都可能是素数”，这个数字实际上是合数的可能性不到百万分之一。

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

回复收藏 0 原文

~没有更多了~