检查一个数是否为素数是否需要减少迭代次数?
例如。 37 是质数,检查 18.5(37 的一半)与 6.08(平方根)之间的关系可以省去很多工作,但两者遵循相同的原则?
不好意思问了,我想巩固一下我用一个数的平方根来判断它是不是素数的逻辑,并试图向其他人解释
最佳答案
之所以有效,是因为如果 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))
,所以检查上限没有意义。
关于algorithm - 使用 N 的平方根与 N/2 相比,检查 N 是否为素数有何优势?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28529695/