[C++知识库]「题目讲解」C语言 使用函数判断素数 求素数和

题目内容

1. 写一个叫prime的函数，传入一个整形值，判断输入的数是不是素数，当传入的数是素数时返回1，否则返回0
2. 写一个叫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;
  }

希望能够帮到大家！