algorithm - 使用 N 的平方根与 N/2 检查 N 是否为质数有什么好处？

Question

是否需要删除迭代来检查一个数字是否是素数？

前任。37 是素数，检查 18.5（37 的一半）与 6.08（平方根）会减少很多工作，但两者都遵循相同的原则？

抱歉问，我试图巩固我使用数字的平方根来确定它是否是质数的逻辑，并试图向其他人解释它

Answer 1

它之所以有效，是因为如果n它可以被 2 整除，那么它也可以被 整除n / 2，如果它不能被一个整除，那么它也不会被另一个整除。所以检查其中一个就足够了，而且检查起来2更方便。

相同的逻辑适用于3：（缺乏）可除性3意味着（缺乏）可除性n / 3，因此仅检查就足够了3。

这同样适用于4, 5, ..., x. 是什么x？这是sqrt(n), 因为n / sqrt(n) = sqrt(n), 所以事情会在这个阈值之后开始重复。

最多检查并包括floor(sqrt(n)). 我们可以证明这一点：

floor(sqrt(n)) <= ceil(sqrt(n))
For the "=" part, it's obvious both work.
floor(sqrt(n)) < ceil(sqrt(n)) <=> floor(sqrt(n)) + 1 = ceil(sqrt(n))

if n divisible by floor(sqrt(n)) + 1 =>
=> n divisible by n / (floor(sqrt(n)) + 1) < n / floor(sqrt(n))

由于我们检查了所有小于或等于 的数字floor(sqrt(n))，我们会找到除数n / (floor(sqrt(n) + 1))，因此检查上限没有意义。

Answer 2

平方根是首选，因为它显着改善了大数的执行时间。

为什么我们可以使用平方根作为极限？如果 N 不是素数，我们可以将其表示为 N = p1*p2，其中 p1 和 p2 的除数大于 1。显然，p1 或 p2（或两者）小于或等于 N 的平方根。所以，它是没有意义的进一步检查。

需要注意的是，确实存在更高级的检查素数的方法。例如：米勒-拉宾素性检验。虽然此测试是概率性的，但通过某些设置，它可以为小于最大 64 位整数的所有素数生成正确答案。