「题目讲解」C语言 使用函数判断素数 求素数和

admin管理员组

文章数量:1794759

「题目讲解」C语言 使用函数判断素数 求素数和

题目内容

写一个叫prime的函数，传入一个整形值，判断输入的数是不是素数，当传入的数是素数时返回1，否则返回0

写一个叫PrimeSum的数，传入两个整形值，其中第一个数要小于第二个数，并求出两个数范围内所有素数的和

测试程序样例 #include <stdio.h> #include <math.h> int prime( int p ); int PrimeSum( int m, int n ); int main() { int m, n, p; scanf("%d %d", &m, &n); printf("Sum of ( "); for( p=m; p<=n; p++ ) { if( prime(p) != 0 ) printf("%d ", p); } printf(") = %d\\n", PrimeSum(m, n)); return 0; }

我们需要在程序后面补充自己需要的代码

输入样例 -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函数

int prime( int p){ int result = 1; for( int i = 2;i < p; i++){ if ( p % i == 0) {result = 0;} } } return result; }

这段代码将输出值默认为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; }

我们尝试跑一下整段代码 输入样例中的结果，不难得到以下输出

Sum of ( -1 0 1 2 3 5 7 ) = 17

等等…看着和之前的答案有些不对？？ -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，结果如下

int prime( int p){ int result = 1; for( int i = 2;i <= sqrt(p); i++){ if ( p % i == 0) { result = 0; } } if (p<=1) { result = 0; } return result; } 总结

利用筛法求素数可以降低代码的时间复杂度 先用prime函数，并在PrimeSum函数中使用prime函数，可以使程序简洁明了

参考答案 #include <stdio.h> #include <math.h> int prime( int p ); int PrimeSum( int m, int n ); int main() { int m, n, p; scanf("%d %d", &m, &n); printf("Sum of ( "); for( p=m; p<=n; p++ ) { if( prime(p) != 0 ) printf("%d ", p); } printf(") = %d\\n", PrimeSum(m, n)); return 0; } int prime( int p){ int result = 1; for( int i = 2;i <= sqrt(p); i++){ if ( p % i == 0) { result = 0; } } if (p<=1) { result = 0; } return result; } int PrimeSum( int m, int n) { int result = 0; for(int i = m; i <= n; i++) { if ( prime(i) == 1) { result += i; } } return result; }

希望能够帮到大家！

本文标签： 素数函数题目语言