C语言求100~~200之间的素数(内含多种优化版本)
2022/1/15 23:33:46
本文主要是介绍C语言求100~~200之间的素数(内含多种优化版本),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
素数又称质数。一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数;否则称为合数。
1.试除法
#include<stdio.h> int main() { int i, j, count = 0; for (i = 101; i < 200; i++) //素数从101开始 { for (j = 2; j < i; j++) //[2,i)的数一一试除 if (i % j == 0) { break; } if (i == j) //如果是素数i=j { printf("%d ", i); count++; } } printf("\n"); printf("%d", count); return 0; }
2.优化一
如果i=101的话[51,101]里面不可能有它的因数,再用[2,i]去试除的话有很多冗余的操作
所以我们采用[2,i/2]这个范围去试除,代码如下
#include<stdio.h> int main() { int i, j, count = 0; for (i = 101; i < 200; i++) { for (j = 2; j < = i/2; j++) //调整为i/2 if (i % j == 0) { break; } if (j > i/2) { printf("%d ", i); count++; } } printf("\n"); printf("%d", count); return 0; }
3.优化二
优化一中还有很多重复操作。我们再思考如果一个数为100 他的平方根是10
2 和50 4和25 5和20都是他的因数,于是我们可以发现试除时只要在[2,sqrt i] 范围内试除就行了
代码如下
int main() { int i, j, count = 0; for (i = 101; i < 200; i++) { for (j = 2; j <= sqrt(i); j++) if (i % j == 0) { break; } if (j > sqrt (i)) { printf("%d ", i); count++; } } printf("\n"); printf("%d", count); return 0; }
4.优化三
只要i不被[2, sqrt(i)]之间的任何数据整除,则i是素数,但是实际在操作时i不用从101逐渐递增到200,因为出了2和3之外,不会有两个连续相邻的数据同时为素数 所以i一次加二
#include<stdio.h> #include <math.h> int main() { int i, j, count = 0; for (i = 101; i < 200; i+=2) { for (j = 2; j <= sqrt(i); j++) if (i % j == 0) { break; } if (j > sqrt (i)) { printf("%d ", i); count++; } } printf("\n"); printf("%d", count); return 0; }
这篇关于C语言求100~~200之间的素数(内含多种优化版本)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-29Elasticsearch慢查询日志配置
- 2024-05-29揭秘华为如此多成功项目的产品关键——Charter模板
- 2024-05-29海外IDC业务拓展的7大挑战
- 2024-05-29InLine Chat功能优化对标Github Copilot,CodeGeeX带来更高效、更直观的编程体验!
- 2024-05-29CodeGeeX 智能编程助手 6 项功能升级,在Visual Studio插件市场霸榜2周!
- 2024-05-29AutoMQ 生态集成 Apache Doris
- 2024-05-292024年IDC行业的深度挖掘:机遇、挑战与未来展望
- 2024-05-29五款扩展组件齐发 —— Volcano、Keda、Crane-scheduler 等,邀你体验
- 2024-05-29AutoMQ 对象存储数据高效组织的秘密: Compaction
- 2024-05-29活动预告|来 GIAC 大会听大数据降本利器:AutoMQ 基于云原生重新设计的 Kafka