判断是否为素数(pascal)

问题描述:

判断是否为素数(pascal)
为什么用穷举法判断的时候,只需用2~sqrt(n)这些数去验证就能证明是否为素数?
1个回答 分类:综合 2014-11-03

问题解答:

我来补答
通俗一点讲:
n的因数都分布在数轴上.
如果n不是完全平方数,那么因数总是成双成对的出现,总有一半因数在sqrt(n)的前面.
如:24
sqrt(24)≈4
24的因数有1,2,3,4,6,8,12,24,可以看出,在sqrt(24)——4以后,每一个24的因数都与4和以前的一个24的因素相对应:1*24=24 2*12=24 3*8=24 4*6=24
所以只要除到sqrt(n),就可以判断是否为质数.
再看完全平方数:试除到sqrt(n)直接可以知道是合数.
如:25
sqrt(25)=5
5就是25的因数
所以用穷举法判断的时候,只需用2~sqrt(n)这些数去验证就能证明是否为素数.
 
 
展开全文阅读
剩余:2000
上一页:一道物理提题
也许感兴趣的知识