是否要消除迭代次数以检查数字是否为质数?
前任。37是一个素数,最多检查18.5(37的一半)和6.08(平方根)会省去很多工作,但是两者遵循相同的原理吗?
抱歉,我正在尝试巩固我的逻辑,即使用数字的平方根来确定它是否为质数,并尝试向他人解释
之所以起作用,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))
,因此检查上限没有任何意义。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句