计算3~n之间所有素数的3到n之间素数平方根之和和,要求:输入n,输出结果注意n应在2~100之间
来源:蜘蛛抓取(WebSpider)
时间:2020-05-01 13:27
标签:
素数的平方根之和
此主题相关图片如下:snap2.jpg
[此贴子已經被作者于 0:45:43编辑过]
-
检验一个数n是否是质数,只要检验n是否能被2到n-1整除就可以,但书上说检验的时候只要检验到n的平方根取整就可以了,即检验2到INT(SQRT(n))就可鉯,为什么呢?
-
定理 如果数n是合数,则必存在一个不大于√n的不等于1的因子.
证明 由n是合数,则必存在大于1的整数p,q使得
由上面定理可知,要检验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就足够了