作业帮筛选法求100内素数为什么要引用#include中的sqrt函数?
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/04 09:23:08
筛选法求100内素数为什么要引用#include中的sqrt函数?
筛选法求100内素数为什么要引用#include中的sqrt函数?
筛选法求100内素数为什么要引用#include中的sqrt函数?
算法中会用到 开方,故要用 sqrt() 函数,而函数的调用必须要依赖 #include 库.
求i到j之间的所有质数
1）最笨的一种方法是把i到j之间的每一个数n,都拿出来,挨个循环用n除以从2到n-1的所有整数,如果期间有一个能整除,那么n是合数,继续下一个.
2）第二种算法效率比这个就高了很多,利用的是一个定理——如果一个数是合数,那么它的最小质因数肯定小于等于他的平方根.比如,50,它的最小质因数是2,它的平方根是7.07xxx,2=q.
如果q根号a,此时更有b > 根号a,于是
a = bq > 根号a·根号a = a
出现矛盾,故q 根号j为止,这样所有为true的数组id（如果i=1则0除外,id从1开始）+i 即为质数.
说的比较复杂,举个例子.例如要查找2－100之间的质数,首先2是质数,把2的倍数去掉(比如4,6,8,...,100,对应的数组位置是a[m-2]即a[2],a[4],a[6],...,a[98],将这些位置设为false)；进行下一步,此时3没有被去掉（a[2]=true）,可认为是质数,所以把3的倍数去掉（a[5]a[8]a[11],...,a[98]=false）；再到5,再到7,7之后呢,因为8,9,10刚才都被去掉了,而100以内的任意合数的最小质数因子肯定小于等于10（100的开方）,所以,去掉,2,3,5,7的倍数后剩下的都是质数了.最后只要将a[id]中所有等于true的id值加上i输出即可.按照这个例子是id+2,比如0+2,1+2,3+2,...
相对来说这种算法求1到n之间的质数实现起来比较简单,如果是求任意两个数之间的质数,逻辑上会比较复杂.但是,效率的确提高了很多很多.