我们需要在程序后面补充自己需要的代码
输入样例 -1 10 输出样例 Sum of ( 2 3 5 7 ) = 17注 题目来源:浙大版《C语言程序设计(第3版)》题目集
解题思路通过观察输出样例,可知我们需要输出给定范围的的所有素数,以及把他们求和的结果
再观察主函数,可知我们传入变量m和n分别作为求素数的范围,变量p作为进行判断一个数是不是素数的变量
主函数中,除了搭建输出框架的"printf"语句和"scanf"语句外,还有一个for循环来进行素数的判断,循环的起始,终止和自加条件可以看出需要对范围内的每一个数进行判断
for循环内嵌套if语句判断是否是素数,其中就包含我们需要写的prime函数
最后一个"printf"语句用到了PrimeSum函数来输出素数和
我们先对需要完成的两个函数进行分析,prime函数可以通过把比自己小的每一个数都进行取余操作来实现,PrimeSum函数可以通过遍历范围内所有的数,把所有的素数相加来实现
我们可以在PrimeSum函数中使用prime函数,来让程序更加简洁,所以先写prime函数
这段代码将输出值默认为1,即默认一个数先是素数,再把比小的数都进行取余,如果有0的结果,把输出值也改为0
这段代码目前看起来没什么问题
再把PrimeSum函数完成
int PrimeSum( int m, int n) { int result = 0; for(int i = m; i <= n; i++) { if ( prime(i) == 1) { result += i; } } return result; }我们尝试跑一下整段代码
输入样例中的结果,不难得到以下输出
等等…看着和之前的答案有些不对??
-1,0,1都是哪门子负数??
仔细一想,我们主函数中把每一个数都进行了素数的判断,如果范围内出现了负数,0和1也会进行判断,所以我们应该完善一下prime函数,把负数,0和1的结果都返回成1,这样输出就对了
代码如下
int prime( int p){ int result = 1; for( int i = 2;i < p; i++){ if ( p % i == 0) { result = 0; } } if (p<=1) { result = 0; } return result;}再次运行,得到结果
Sum of ( 2 3 5 7 ) = 17 方法优化这回结果应该是对了,但prime函数中,判断素数的方法,完全没有必要循环到p,甚至循环到p/2都足够
这里补充一种求素数的方法,筛法,即挨拉托色尼筛法,把从2到N的一组正整数从小到大按顺序排列。从中依次删除2的倍数、3的倍数、5的倍数,直到根号N的倍数为止,剩余的即为2~N之间的所有素数。
所以我们可以利用开始的math.h方法库,把循环的结束条件设置到根号p,结果如下
利用筛法求素数可以降低代码的时间复杂度
先用prime函数,并在PrimeSum函数中使用prime函数,可以使程序简洁明了
希望能够帮到大家!