C语言求100~200之间的素数(逐步优化)

   日期:2024-12-26    作者:wfzzm 移动:http://mip.riyuangf.com/mobile/quote/54315.html

思路
素数:即质数,除了1和自己之外,再没有其他的约数,则该数据为素数,具体方式如下

C语言求100~200之间的素数(逐步优化)

方法一:试除法

 

上述方法的缺陷:超过i一半的数据,肯定不是i的倍数,上述进行了许多没有意义的运算,因此可以采用如下
方式进行优化

方法二:每拿到一个数据,只需要检测其:[2, i/2]区间内是否有元素可以被2i整除即可,可以说明i不是素数

 

方法二还是包含了一些重复的数据,再优化

方法三
如果i能够被[2, sqrt(i)]之间的任意数据整除,则i不是素数
原因:如果 m 能被 2 ~ m-1 之间任一整数整除,其二个因子必定有一个小于或等于sqrt(m),另一个大于或等于 sqrt(m)。

 

方法4
继续对方法三优化,只要i不被[2, sqrt(i)]之间的任何数据整除,则i是素数,但是实际在操作时i不用从101逐渐递增到200,因为出了2和3之外,不会有两个连续相邻的数据同时为素数


 

特别提示:本信息由相关用户自行提供,真实性未证实,仅供参考。请谨慎采用,风险自负。


举报收藏 0评论 0
0相关评论
相关最新动态
推荐最新动态
点击排行
{
网站首页  |  关于我们  |  联系方式  |  使用协议  |  隐私政策  |  版权隐私  |  网站地图  |  排名推广  |  广告服务  |  积分换礼  |  网站留言  |  RSS订阅  |  违规举报  |  鄂ICP备2020018471号