algorithm - 使用 N 的平方根与 N/2 相比，检查 N 是否为素数有何优势？

Question

检查一个数是否为素数是否需要减少迭代次数？

例如。 37 是质数，检查 18.5(37 的一半)与 6.08(平方根)之间的关系可以省去很多工作，但两者遵循相同的原则？

不好意思问了，我想巩固一下我用一个数的平方根来判断它是不是素数的逻辑，并试图向其他人解释

Answer 1

之所以有效，是因为如果 n 可以被 2 整除那么它也可以被 n/2 整除，如果它不能被 1 整除，它就不会被可以被另一个整除。所以查其中一个就够了，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)) ，所以检查上限没有意义。