习题5

admin管理员组

文章数量:1794759

习题5

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

素数就是只能被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; }

本文标签： 习题