找到小于给定数字 n 的最接近素数的最有效算法是什么？
问题
给定数字 n，2<=n<=2^63。 n 本身可以是素数。找到最接近 n 的素数 p。
利用以下事实：对于所有素数 p，p>2，p 是奇数并且 p 的形式为 6k+1 或 6k+5，可以编写一个从 n−1 到 2 的循环来检查该数字是否是素数。因此，我不需要检查所有数字，而是需要检查上述两种形式中的每一个奇数。不过我想知道是否有更快的算法来解决这个问题？即需要检查一些可以限制数字范围的约束？任何想法将不胜感激。
Problem
Given a number n, 2<=n<=2^63. n could be prime itself. Find the prime p that is closest to n.
Using the fact that for all primes p, p>2, p is odd and p is of the form 6k+1 or 6k+5, one could write a loop from n−1 to 2 to check if that number is prime. So instead of checking for all numbers I need to check for every odd of the two forms above. However, I wonder if there is a faster algorithm to solve this problem? i.e. some constraints that can restrict the range of numbers need to be checked? Any idea would be greatly appreciated.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
实际上，找到素数的几率“很高”，因此根据我们迄今为止对数论的了解，在跳过“琐碎”数字（可被小素数整除的数字）的同时进行强力检查将是最好的方法。
[更新]您可能会做的温和优化类似于埃拉托色尼筛法，您定义一些小的平滑边界并将 N 范围内的所有数字标记为复合数字，并且仅测试与平滑基数互质的数字。您需要使范围和平滑度足够小，以免使相对“昂贵”的主要测试的运行时间黯然失色。
In reality, the odds of finding a prime number are "high" so brute force checking while skipping "trivial" numbers (numbers divisible by small primes) is going to be your best approach given what we know about number theory to date.
[update] A mild optimization that you might do is similar to the Sieve of Eratosthenes where you define some small smooth bound and mark all numbers in a range about N as being composite and only test the numbers relatively prime to your smooth base. You will need to make your range and smoothness small enough as to not eclipse the runtime of the comparatively "expense" prime test.
您可以做的最大优化是在进行完整测试之前使用快速素性检查。例如，请参阅 http://en.wikipedia.org/wiki/Miller%E2% 80%93Rabin_primality_test 用于常用测试，可以快速消除大多数“可能不是素数”的数字。只有当你有充分的理由相信一个数是素数之后，你才应该尝试正确地证明素数。 （出于许多目的，人们很乐意接受这样的事实：如果它通过了拉宾-米勒检验的固定次数的试验，那么它很可能是素数，因此您可以接受这个事实。）
The biggest optimization that you can do is to use a fast primality check before doing a full test. For instance see http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test for a commonly used test that will quickly eliminate most numbers as "probably not prime". Only after you have good reason to believe that a number is prime should you attempt to properly prove primality. (For many purposes people are happy to just accept that if it passes a fixed number of trials of the Rabin-Miller test, it is so likely to be prime that you can just accept that fact.)