检验一个数n是否是质数,只要检验n是否能被2到n-1整除就可以,但书上说检验的时候只要检验到n的平方根取整就可以了,即检验2到INT(SQRT(n))就可以,为什么呢?
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/06 12:06:33
![检验一个数n是否是质数,只要检验n是否能被2到n-1整除就可以,但书上说检验的时候只要检验到n的平方根取整就可以了,即检验2到INT(SQRT(n))就可以,为什么呢?](/uploads/image/z/3710362-58-2.jpg?t=%E6%A3%80%E9%AA%8C%E4%B8%80%E4%B8%AA%E6%95%B0n%E6%98%AF%E5%90%A6%E6%98%AF%E8%B4%A8%E6%95%B0%2C%E5%8F%AA%E8%A6%81%E6%A3%80%E9%AA%8Cn%E6%98%AF%E5%90%A6%E8%83%BD%E8%A2%AB2%E5%88%B0n-1%E6%95%B4%E9%99%A4%E5%B0%B1%E5%8F%AF%E4%BB%A5%2C%E4%BD%86%E4%B9%A6%E4%B8%8A%E8%AF%B4%E6%A3%80%E9%AA%8C%E7%9A%84%E6%97%B6%E5%80%99%E5%8F%AA%E8%A6%81%E6%A3%80%E9%AA%8C%E5%88%B0n%E7%9A%84%E5%B9%B3%E6%96%B9%E6%A0%B9%E5%8F%96%E6%95%B4%E5%B0%B1%E5%8F%AF%E4%BB%A5%E4%BA%86%2C%E5%8D%B3%E6%A3%80%E9%AA%8C2%E5%88%B0INT%28SQRT%28n%29%29%E5%B0%B1%E5%8F%AF%E4%BB%A5%2C%E4%B8%BA%E4%BB%80%E4%B9%88%E5%91%A2%3F)
检验一个数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))就可以了