北京电子科技学院（BESTI）
实验报告
实验内容
素数（Prime Number），又称为质数，它是不能被1和它本身以外的其他整数整除的正整数。按照这个定义，负数、0和1都不是素数，而17之所以是素数，是因为除了1和17以外，它不能被2～16之间的任何整数整除。
任务1：试商法是最简单的判断素数的方法。用i=2~m-1之间的整数去试商，若存在某个m能被1与m本身以外的整数i整除（即余数为0），则m不是素数，若上述范围内的所有整数都不能整除m，则m是素数。采用试商法，分别用goto语句、break语句和采用设置标志变量并加强循环测试等三种方法编写素数判断函数IsPrime()，从键盘任意输入一个整数m，判断m是否为素数，如果m是素数，则按"%d is a prime number\n"格式打印该数是素数，否则按"%d is not a prime number\n"格式打印该数不是素数。然后分析哪一种方法可读性更好。
1、 goto语句
#include <stdio.h>
#include <stdlib.h>
int IsPrime(int n); //判断是否是素数的函数原型
int main()
{
int m;
printf("Please enter a integer:");
scanf("%d", &m); //用户输入欲判断的数
if( IsPrime(m) == 1){ //调用判断是否是素数的函数并输出结果
printf("%d is a prime number!\n", m);
}
else{
printf("%d is not a prime number!\n", m);
}
return 0; //返回0
} //主函数结束
int IsPrime(int n) //判断是否是素数的函数
{
int i = 2;
int j = 0;
if(n < 2){ //若n小于2，返回0值
return 0;
}
if(n == 2){
return 1;
}
loop:if(n % i == 0){ //利用goto语句
i++;
j++;
goto loop;
}
if(j >= 1){ //若j大于2，则说明能被2~n-1之间的数整除，返回0；否则返回1
return 0;
}
else{
return 1;
}
} //子函数结束
2、 break语句
#include <stdio.h>
#include <stdlib.h>
int IsPrime(int n); //判断是否是素数的函数原型
int main()
{
int m;
printf("Please enter a integer:");
scanf("%d", &m); //用户输入欲判断的数
if( IsPrime(m) == 1){ //调用判断是否是素数的函数并输出结果
printf("%d is a prime number\n", m);
}
else{
printf("%d is not a prime number\n,", m);
}
return 0; //返回0
} //主函数结束
int IsPrime(int n) //判断是否是素数的函数
{
int i;
int j = 0;
if( n < 2 ){ //若n小于2，返回0值
return 0;
}
for(i = 2; i <= n - 1; i++){
if( n % i == 0){ //利用试商法判断是否能被2~n-1之间的数整除
j++;
}
if(j > 1){ //若j大于2，则说明能被2~n-1之间的数整除，返回0；否则返回1
return 0;
break;
}
}
if( j == 0)
return 1;
} //子函数结束
3、采用设置标志变量并加强循环测试
#include <stdio.h>
#include <stdlib.h>
int IsPrime(int n); //判断是否是素数的函数原型
int main()
{
int m;
printf("Please enter a integer:");
scanf("%d", &m); //用户输入欲判断的数
if( IsPrime(m) == 1){ //调用判断是否是素数的函数并输出结果
printf("%d is a prime number\n", m);
}
else{
printf("%d is not a prime number\n,", m);
}
return 0; //返回0
} //主函数结束
int IsPrime(int n) //判断是否是素数的函数
{
int i;
int j = 0;
if( n < 2 ){ //若n小于2，返回0值
return 0;
}
for(i = 2; i <= n - 1; i++){
if( n % i == 0){ //利用试商法判断是否能被2~n-1之间的数整除
j++;
}
}
if(j >= 1){ //若j大于2，则说明能被2~n-1之间的数整除，返回0；否则返回1
return 0;
}
else{
return 1;
}
} //子函数结束
任务2：用数学的方法可以证明，不能被2～
（取整）之间的数整除的数，一定不能被1和它本身之外的其他任何整数整除。根据素数的这个性质，通过修改素数判断函数IsPrime()的具体实现，编程完成任务1。
#include <stdio.h>
#include <stdlib.h>
#include <math.h> //因调用 sqrt()函数，故需此预处理命令
int IsPrime(int n); //判断是否是素数的函数原型
int main()
{
int m;
printf("Please enter a integer:");
scanf("%d", &m); //用户输入欲判断的数
if( IsPrime(m) == 1){ //调用判断是否是素数的函数并输出结果
printf("%d is a prime number\n", m);
}
else{
printf("%d is not a prime number\n,", m);
}
return 0; //返回0
} //主函数结束
int IsPrime(int n) //判断是否是素数的函数
{
int i;
int j = 0;
if( n < 2 ){ //若n小于2，返回0值
return 0;
}
for(i = 2; i <= sqrt(n); i++){
if( n % i == 0){ //利用试商法判断是否能被2~ n的开方（取整）之间的数整除
j++;
}
}
if(j >= 1){ //若j大于2，则说明能被2~n-1之间的数整除，返回0；否则返回1
return 0;
}
else{
return 1;
}
} //子函数结束
任务3：从键盘任意输入一个整数n，编程计算并输出1~n之间的所有素数之和。
#include <stdio.h>
#include <stdlib.h>
#include <math.h> //因调用 sqrt()函数，故需此预处理命令
int IsPrime(int m); //判断是否是素数并求和的函数原型
int main()
{
int n;
printf("Please enter a integer:");
scanf("%d", &n); //用户输入欲判断的数
//打印输出1~n之间的所有素数之和
printf("The sum of all the primes between 1 and the number you enter is: %d\n", IsPrime(n));
return 0; //返回0
} //主函数结束
int IsPrime(int m) //判断是否是素数的函数
{
int i;
int j;
int sum = 0;
for(i = 2; i <= m; i++){
int k = 0;
for(j = 2; j <= sqrt(i); j++){
if( i % j == 0){ //利用试商法判断是否能被2~ n的开方（取整）之间的数整除
k++;
}
}
if(k == 0){ //如果k等于0，说明i是素数，求和
sum = sum +i;
}
}
return sum; //返回素数之和
} //子函数结束
任务4：从键盘任意输入一个整数m，若m不是素数，则计算并输出其所有的因子（不包括1），例如对于16，输出2，4，8；否则输出"No divisor! It is a prime number\n"。
#include <stdio.h>
#include <stdlib.h>
#include <math.h> //因调用 sqrt()函数，故需此预处理命令
int IsPrime(int n); //判断是否是素数的函数原型
int main()
{
int m;
int i;
printf("Please enter a integer:");
scanf("%d", &m); //用户输入欲判断的数
if(IsPrime(m) == 1){ //调用判断是否是素数的函数，若不是素数，打印因子（不包括1）
for(i = 2; i <= m; i++){
if( m % i == 0){ //利用试商法判断是否是因子
printf("%d ", i);
}
}
}
if(IsPrime(m) == 0){ //调用判断是否是素数的函数并输出结果
printf("No divisor! It is a prime number\n");
}
return 0; //返回0
} //主函数结束
int IsPrime(int n) //判断是否是素数的函数
{
int i;
int j = 0;
for(i = 2; i <= sqrt(n); i++){
if( n % i == 0){ //利用试商法判断是否能被2~ n的开方（取整）之间的数整除
j++;
}
}
if(j >= 1){ //若j大于2，则说明能被2~n-1之间的数整除，返回1；否则返回0
return 1;
}
else{
return 0;
}
} //子函数结束
任务5：如果一个正整数m的所有小于m的不同因子（包括1）加起来正好等于m本身，那么就被称它为完全数（Perfect Number）。例如，6就是一个完全数，是因为6 = 1 + 2 + 3。请编写一个判断完全数的函数IsPerfect()，然后判断从键盘输入的整数是否是完全数。
#include <stdio.h>
#include <stdlib.h>
int IsPerfect(int n); //判断输入的整数是否是完全数的函数原型
int main()
{
int m;
printf("Please enter a integer:");
scanf("%d", &m); //用户输入欲判断的数
if(IsPerfect(m) == 1){ //调用判断是否是素数的函数，若是，打印语句
printf("The number you enter is a Perfect Number!\n");
}
if(IsPerfect(m) == 0){ //调用判断是否是素数的函数，若不是，打印语句
printf("The number you enter is not a Perfect Number!\n");
}
return 0; //返回0
} //主函数结束
int IsPerfect(int n) //判断输入的整数是否是完全数的函数
{
int i;
int sum = 0;
for(i = 1; i < n; i++){
if(n % i == 0){ //判断是否是因子
sum = sum + i; //求因子之和
}
}
if(sum == n){ //判断输入的整数是否是完全数
return 1;
}
else
return 0;
} //子函数结束
任务6：从键盘任意输入一个整数m，若m不是素数，则对m进行质因数分解，并将m表示为质因数从小到大顺序排列的乘积形式输出，否则输出"It is a prime number\n"。例如，用户输入90时，程序输出90 = 2 * 3 * 3 * 5；用户输入91时，程序输出"It is a prime number\n"。
#include <stdio.h>
#include <stdlib.h>
#include <math.h> //因调用 sqrt()函数，故需此预处理命令
int IsPrime1(int x); //判断是否是素数的函数原型
int IsPrime2(int y); //判断是否是素数的函数原型
int main()
{
int m;
int a = 1; //a表示质因数之积
int b; //b表示m与其因数之商
printf("Please enter a integer:");
scanf("%d", &m); //用户输入欲判断的数
if(IsPrime1(m) == 1){ //调用判断是否是素数的函数，若是，打印语句
printf("It is a prime number!\n");
}
//调用判断是否是素数的函数，若不是将m表示为质因数从小到大顺序排列的乘积形式输出
if(IsPrime1(m) == 0){
printf("%d =", m);
while(a != m){ //判断所有因子之积是否等于m，不等继续运行
b = m / a;
printf(" %d ", IsPrime2(b)); //打印因子
a = IsPrime2(b) * a; //m的因子之积
if(a != m){
printf("*"); //打印乘号
}
}
}
return 0;
}
int IsPrime1(int x) //判断是否是素数的函数
{
int i;
int j = 0;
for(i = 1; i <= sqrt(x); i++){
if(x % i == 0){ //利用试商法判断是否能被2~ n的开方（取整）之间的数整除
j++;
}
}
if(j <= 1){ //若j小于2，则说明能被2~ n的开方（取整）之间的数整除，返回1；否则返回0
return 1;
}
else
return 0;
} //子函数结束
int IsPrime2(int y) //判断是否是素数的函数
{
int i;
int j;
for(i = 2; i <= y; i++){ //找出2~y之间的素数
int k = 0;
for(j = 2; j <= sqrt(i); j++){
if( i % j == 0){ //利用试商法判断是否能被2~ i的开方（取整）之间的数整除
k++;
}
}
if(k == 0 && y % i == 0){
return i;
}
}
}
任务7： 验证：2000以内的正偶数都能够分解为两个素数之和（即验证哥德巴赫猜想对2000以内的正偶数成立），正奇数都能够分解为三个素数之和。注意最后要将结果上传之前，请将2000改为500再运行，并注意输出格式，每行5个等式，如：10=3+7；12=5+7；…。
#include <stdio.h>
#include <stdlib.h>
#include <math.h> //因调用 sqrt()函数，故需此预处理命令
int IsPrime1(int x); //输出正偶数分解为两个素数之和的函数原型
int IsPrime2(int y); //输出正奇数分解为三个素数之和的函数原型
int main()
{
int m; //定义整型变量，为偶数
int n; //定义整型变量，为奇数
printf("正偶数等于两素数之和：\n");
for(m = 2; m <= 100; m += 2){ //输出正偶数分解为两个素数之和
IsPrime1(m);
}
printf("\n正奇数等于三素数之和：\n");
for(n = 5; n <= 100; n += 2){ //输出正奇数分解为三个素数之和
IsPrime2(n);
}
return 0; //返回0
} //主函数结束
int IsPrime1(int x) //输出正偶数分解为两个素数之和的函数
{
int i; //i表示素数
int j; //j用于判断i是否是素数
int a; //a表示素数
int b; //b用于判断a是否是素数
if(x % 5 == 4){
printf("\n");
}
for(i = 2; i <= x; i++){ //判断i是2~y之间的素数
int k1 = 0;
for(j = 2; j <= sqrt(i); j++){
if( i % j == 0){
k1++;
}
}
if(k1 == 0){
for(b = 2; b <= x; b++){ //判断b是2~y之间的素数
int k2 = 0;
for(a = 2; a <= sqrt(b); a++){
if( b % a == 0){
k2++;
}
}
if( k2 == 0){
if(i + b == x){ //如果i、b都是素数，求和判断是否等于x，若等打印
printf("%d = %d + %d; ", x, i, b);
}
if(i + b == x){
return 0;
}
} //if结束
} //for循环结束
} //if结束
} //for循环结束
return 0; //返回0
} //主函数结束
int IsPrime2(int y) //输出正奇数分解为三个素数之和的函数
{
int i; //i表示素数
int j; //j用于判断i是否是素数
int a; //a表示素数
int b; //b用于判断a是否是素数
int g; //g表示素数
int h; //h用于判断g是否是素数
if(y % 5 == 2){
printf("\n");
}
for(i = 2; i <= y; i++){ //判断i是2~y之间的素数
int k1 = 0;
for(j = 2; j <= sqrt(i); j++){
if( i % j == 0){
k1++;
}
}
if(k1 == 0){
for(b = 2; b <= y; b++){ //判断b是2~y之间的素数
int k2 = 0;
for(a = 2; a <= sqrt(b); a++){
if( b % a == 0){
k2++;
}
}
if( k2 == 0){
for(g = 2; g <= y; g++){ //判断g是2~y之间的素数
int k3 = 0;
for(h = 2; h <= sqrt(g); h++){
if( g % h == 0){
k3++;
}
}
if(k3 == 0){
if(i + b + g == y){ //如果i、b、g都是素数，求和判断是否等于y，若等打印
printf("%d = %d + %d + %d; ", y, i, b, g);
}
if(i + b + g == y){ //用于终止循环
return 0;
}
} //if结束
} //for循环结束
} // if结束
} //for循环结束
} //if结束
} //for循环结束
return 0;
} //子函数结束