作业帮检验一个数n是否是质数,只要检验n是否能被2到n-1整除就可以,但书上说检验的时候只要检验到n的平方根取整就可以了,即检验2到INT(SQRT(n))就可以,为什么呢?
来源：学生作业帮助网 编辑：作业帮 时间：2024/11/08 14:43:24
检验一个数n是否是质数,只要检验n是否能被2到n-1整除就可以,但书上说检验的时候只要检验到n的平方根取整就可以了,即检验2到INT(SQRT(n))就可以,为什么呢?
检验一个数n是否是质数,只要检验n是否能被2到n-1整除就可以,但书上说检验的时候只要检验到n的平方根取整就可以了,即检验2到INT(SQRT(n))就可以,为什么呢?
检验一个数n是否是质数,只要检验n是否能被2到n-1整除就可以,但书上说检验的时候只要检验到n的平方根取整就可以了,即检验2到INT(SQRT(n))就可以,为什么呢?
定理 如果数n是合数,则必存在一个不大于√n的不等于1的因子.
证明 由n是合数,则必存在大于1的整数p,q使得
n=pq
如果p,q均大于n,即p>√n,q>√n,则必有pq>√n√n=n,这与n=pq矛盾.
由上面定理可知,要检验n是否是质数,只需从2开始试除,直到不超过√n的整数试除为止,如果均不能除尽,n必是质数,如果是合数它一定会被一个不超过√n的整数除尽.
如果一个大于SQR的数a是n的质因数，那么s/a必然是一个小于SQR的整数，设其为b。那么当检查到b的时候（从小到大的顺序，b一定在SQR之前，当然也在a之前）就应当发现n不是质数，因为b是n的质因数，并且同时能够知道a=n/b也是n的质因数
因此只需要检查到SQR就足够了...
全部展开
如果一个大于SQR的数a是n的质因数，那么s/a必然是一个小于SQR的整数，设其为b。那么当检查到b的时候（从小到大的顺序，b一定在SQR之前，当然也在a之前）就应当发现n不是质数，因为b是n的质因数，并且同时能够知道a=n/b也是n的质因数
因此只需要检查到SQR就足够了
收起
比如检验33是否质数，2、3、4、5、都试过了，5后面就不必试了，因为如果试6，7，8.....还有可能被整除，那么商应该在5以内， 可是已经试过了。
一个数n如果能被>=(n的平方根取整+1)的数整除,那所得的商必<=n的平方根取整,也就是说它可以被这个商整除.
因此只要检验到n的平方根取整就可以了.
比如：12的因子：1，2，3，4，6，12
12/1=12
12/12=1
12/2=6
12/6=2
12/3=4
12/4=3
重复的因此2到INT(SQRT(n))就可以了