习题5-4 使用函数求素数和

本题要求实现一个判断素数的简单函数、以及利用该函数计算给定区间内素数和的函数。

素数就是只能被1和自身整除的正整数。注意：1不是素数，2是素数。

函数接口定义：

int prime( int p );
int PrimeSum( int m, int n );

其中函数prime当用户传入参数p为素数时返回1，否则返回0；函数PrimeSum返回区间[m, n]内所有素数的和。题目保证用户传入的参数m≤n。

裁判测试程序样例：

#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

解题思路：

        依题，我们可以知道 prime 函数是判断函数，用于判断一个数是否为素数，是素数时返回1，否则返回0；PrimeSum 函数是计算函数，用于计算 m 到 n 内所有素数的和。首先，我们来判断一个数是否为素数。判断一个数是否为素数的方法有两种。

        第一，依题，素数是只能被 1 和自身整除的正整数（ 1 不是素数，2 是素数），因此，判断一个整数 p 是否是素数，我们可以让 p 除以 2 ~ p-1 之间的所有整数，如果都不能被整除，那么 p 就是一个素数。首先判断 p 的值，如果 p 小于2，则不是素数，返回0。如果 p=2，是素数，返回1。接着讨论 p>2 的情况，定义一个数 a=0，用 for 循环让 p 除以 2~p-1 之间的所有整数，若能被整除，则 a+1。循环结束后，判断 a 的值，如果 a=0，说明在循环中没有任意一个整数能被 p 整除，即 p 是素数，返回 1 ；如果  ，说明在循环中，至少有一个数让 p 整除了，即 p 不是素数，返回 0。

        第二，这一个方法有一点巧妙。即 p 不需要除以 2~p-1 之间的所有整数，因为头文件里调用了 math.h，所以我们只需要用 p 除以 2~ 之间的所有整数，如果都不能被整除，那么 p 就是一个素数。定义一个数 a 用来存储  ，注意函数 sqrt() 的参数为 double 类型，这里要强制转换 p 的类型。然后用 for 循环，让 p 除以 2~   之间的所有整数，若能被整除，则退出循环。这时如果 i>a，说明循环正常结束了，2~  内没有任何一个整数能让 p 整除，即 p 是一个素数，返回1；否则返回0。

        接下来是 PrimeSum 函数，这个函数用于计算 m 到 n 内所有素数的和。定义一个变量 sum 用于储存和。因为 2 以下不是素数，所以当 m 小于2 时可以直接让 m=2 ，接着是 for 循环，从 m 开始，到 n，每次循环结束时 m+1，当 prime 函数返回 1 时，将 m 加入 sum。最后返回 sum。

具体代码：

方法一

int prime( int p )
{
    int a=0;
    if(p<2) return 0;    // m<2时不是素数，直接返回0
    else if(p==2) return 1; //m=2时直接返回1
    else{
        for(int i=2;i<p;i++){   // p 除以 2 ~ p-1 之间的所有整数，若能被整除，则 a+1
            if( p%i==0)
                a++;
        }
        //如果 a=0，说明在循环中没有任意一个整数能被 p 整除，即 p 是素数，返回 1
        if(a==0) return 1;
        //否则返回 0
        else return 0;
    }

}

int PrimeSum( int m, int n )
{
    int sum=0;
    if(m<0) m=2;
    for( m; m<=n; m++)
    {
        if(prime(m)==1)
            sum=sum+m;
    }
    return sum;
}

 方法二

int prime( int p )
{
    if(p<2) return 0;      // m<2时不是素数，直接返回0
    else if(p==2) return 1;  //m=2时直接返回1
    else{
        // 求平方根，注意sqrt()的参数为 double 类型，这里要强制转换m的类型 
        int a = (int)sqrt( (double)p );
        int i;
        //让 p 除以 2 ~ 根号p  之间的所有整数，若能被整除，则退出循环。
        for( i=2; i<=a; i++ ){
            if( (int)p%i==0 )
                break;
        }
//如果 i>a，说明循环正常结束了，2~ 根号p 内没有任何一个整数能让 p 整除，即 p 是一个素数，返回1
        if( i>a ) return 1;
        else return 0;
    }
    
}

int PrimeSum( int m, int n )
{
    int sum=0;
    if(m<0) m=2;
    for( m; m<=n; m++)
    {
        if(prime(m)==1)
            sum=sum+m;
    }
    return sum;
}