使用N与N / 2的平方根来检查N是否是质数有什么优势?

斯密蒂·韦本杰格曼·詹森(Smitty Werbenjagermanjensen)

是否要消除迭代次数以检查数字是否为质数?

前任。37是一个素数,最多检查18.5(37的一半)和6.08(平方根)会省去很多工作,但是两者遵循相同的原理吗?

抱歉,我正在尝试巩固我的逻辑,即使用数字的平方根来确定它是否为质数,并尝试向他人解释

伊夫拉德

之所以起作用,n因为如果被2整除,那么它也可以被整除n / 2,如果不能被一个整除,则也不能被另一个整除。因此,检查其中之一就足够了,并且检查起来2更方便。

相同的逻辑适用于3:(缺少)可除性3意味着(缺少)可除性n / 3,因此仅检查即可3

同样适用4, 5, ..., x什么xsqrt(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] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章