计算3~n之间所有素数的3到n之间素数平方根之和和,要求:输入n,输出结果注意n应在2~100之间

此主题相关图片如下: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就足够了

我要回帖

更多关于 素数的平方根之和 的文章

 

随机推荐