筛选法求100内素数为什么要引用#include中的sqrt函数?
来源:学生作业帮 编辑:搜搜考试网作业帮 分类:综合作业 时间:2024/06/26 03:00:12
筛选法求100内素数为什么要引用#include中的sqrt函数?
![筛选法求100内素数为什么要引用#include中的sqrt函数?](/uploads/image/z/15054002-26-2.jpg?t=%E7%AD%9B%E9%80%89%E6%B3%95%E6%B1%82100%E5%86%85%E7%B4%A0%E6%95%B0%E4%B8%BA%E4%BB%80%E4%B9%88%E8%A6%81%E5%BC%95%E7%94%A8%23include%E4%B8%AD%E7%9A%84sqrt%E5%87%BD%E6%95%B0%3F)
算法中会用到 开方,故要用 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之间的质数实现起来比较简单,如果是求任意两个数之间的质数,逻辑上会比较复杂.但是,效率的确提高了很多很多.
求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之间的质数实现起来比较简单,如果是求任意两个数之间的质数,逻辑上会比较复杂.但是,效率的确提高了很多很多.