C语言程序设计100例之（11）：求质数
例11 求质数
问题描述
质数是指除了有1和自身作为约数外，不再有其他约数的数。比如：3、5、7是质数。而9不是质数，因为它还有约数3。
编写程序求给定区间中的所有质数。
输入格式
两个整数a和b，其中1≤a≤b≤100000。
输出格式
输出给定范围的所有质数，输出时每个质数占5列，每行输出10个质数。
输入样例
100 200
输出样例
101 103 107 109 113 127 131 137 139 149
151 157 163 167 173 179 181 191 193 197
199
（1）编程思路
判断一个数m是否为质数的方法是：用2~sqrt(m)中的每一个整数i去除m，若某一个i能整除m，则m不是质数；否则，m是质数。该操作可定义为一个函数，如下：
int isPrime(int m)
{
int i;
if (m==1) return 0;
for (i=2;i<=sqrt(1.0*m);i++)
if (m%i==0) return 0;
return 1;
}
求a~b之间的所有质数，写成一个循环，在循环中调用函数isPrime判断每个整数i是否为质数，若是，则计数并输出。
（2）源程序。
#include <stdio.h>
#include <math.h>
int isPrime(int m)
{
int i;
if (m==1) return 0;
for (i=2;i<=sqrt(1.0*m);i++)
if (m%i==0) return 0;
return 1;
}
int main()
{
int i,a,b,cnt=0;
scanf("%d%d",&a,&b);
for (i=a;i<=b;i++)
{
if (isPrime(i))
{
cnt++;
printf("%5d",i);
if (cnt%10==0) printf("\n");
}
}
return 0;
}
习题11
11-1 回文质数
问题描述
我国古代有一种回文诗，倒念顺念都有意思，例如“人过大佛寺”，倒读起来便是“寺佛大过人”。还有经典的对联“客上天然居，居然天上客”等。在自然数中，如果一个数从左向右读或是从右向左读完全一致，这样的自然数称为回文数。
编写一个程序，找出N之内的所有回文质数。所谓回文质数就是一个数即是一个质数又是一个回文数，例如，151 是回文质数。
输入格式
一个整数N，其中1≤N≤100000。
输出格式
输出N以内的所有回文质数，输出时每个回文质数占5列，每行输出10个回文质数。
输入样例
10000
输出样例
2 3 5 7 11 101 131 151 181 191
313 353 373 383 727 757 787 797 919 929
（1）编程思路。
将判断一个数是否为质数和是否为回文数分别写成一个函数。
函数int isPrime(int m);判断数m是否为质数，m是质数，函数返回值为1，否则为0。
函数int isPalm(int m); 判断数m是否为回文数，m是回文数，函数返回值为1，否则为0。
（2）源程序。
#include <stdio.h>
#include <math.h>
int isPrime(int m)
{
int i;
if (m==1) return 0;
for (i=2;i<=sqrt(1.0*m);i++)
if (m%i==0) return 0;
return 1;
}
int isPalm(int m) // 判断m是否为回文数
{
int a,b;
a=m; b=0;
while (a>0)
{
b=b*10+a%10 ;
a = a/10;
}
return b==m;
}
int main()
{
int i,n,cnt=0;
scanf("%d",&n);
for (i=1;i<=n;i++)
{
if (isPalm(i) && isPrime(i))
{
cnt++;
printf("%5d",i);
if (cnt%10==0) printf("\n");
}
}
return 0;
}
从程序运行结果可以看出，回文质数除了11以外，所有回文质数的位数都是奇数。这是因为，如果一个回文数的位数是偶数，则它的奇数位上的数字之和与偶数位上的数字之和必然相等。根据数的整除性原理，这样的数肯定能被11整除。因此，回文质数的位数绝不可能是偶数（除11外）。
11-2 第N个质数
问题描述
质数就是不能再进行等分的整数。比如：7，11是质数。而9不是质数，因为它可以平分为3等份。一般认为最小的质数是2，接着是3，5，...
设“2” 是第一个质数，“3” 是第二个质数，依此类推。问第N个质数是多少？
输入格式
一个整数N，其中1≤N≤1000000。
输出格式
一个整数，它是第N个质数。
输入样例
10
输出样例
29
（1）编程思路。
先处理n=1，输出2的特殊情况。因为，2之后的所有质数均为奇数。
记当前质数个数cnt=1（2是第1个质数），从i=3开始，顺序判断当前奇数是否为质数，若是质数则cnt++，若cnt==n，则当前奇数为第n个质数，结束循环查找并输出结果。
（2）源程序。
#include <stdio.h>
#include <math.h>
int isPrime(int m)
{
int i;
if (m==1) return 0;
for (i=2;i<=sqrt(1.0*m);i++)
if (m%i==0) return 0;
return 1;
}
int main()
{
int n,i,cnt;
scanf("%d",&n);
if (n==1) printf("2\n");
else
{
cnt=1; i=3;
while(1)
{
if (isPrime(i)) cnt++;
if(cnt==n) break;
i+=2;
}
printf("%d\n",i);
}
return 0;
}
11-3 哥德巴赫猜想（升级版）
题目描述
1742年6月7日哥德巴赫写信给当时的大数学家欧拉，正式提出了以下的猜想：任何一个大于9的奇数都可以表示成3个质数之和。质数是指除了1和本身之外没有其他约数的数，如2和11都是质数，而6不是质数，因为6除了约数1和6之外还有约数2和3。需要特别说明的是1不是质数。
这就是哥德巴赫猜想。欧拉在回信中说，他相信这个猜想是正确的，但他不能证明。
从此，这道数学难题引起了几乎所有数学家的注意。哥德巴赫猜想由此成为数学皇冠上一颗可望不可及的“明珠”。
现在请你编一个程序验证哥德巴赫猜想。
输入格式
仅有一行，包含一个正奇数n，其中9<n<20000。
输出格式
仅有一行，输出3个质数，这3个质数之和等于输入的奇数。相邻两个质数之间用一个空格隔开，最后一个质数后面没有空格。如果表示方法不唯一，请输出第一个质数最小的方案，如果第一个质数最小的方案不唯一，请输出第一个质数最小的同时，第二个质数最小的方案。
输入样例
2009
输出样例
3 3 2003
（1）编程思路。
对输入的正奇数n，先判断其和是否含有质数2，只有一种可能2+2+（n-4），若n-4是质数，则直接输出结果，结束。
如果n的和值中不包含质数2，则只能分解为3个奇数之和。不妨设n=i+j+(n-i-j)。用一个二重循环寻找答案。外循环i为3~n/3之间的所有奇数，内循环j为i~n/3之间的所有奇数，在内循环中调用函数isPrime判断，若i、j、n-i-j三个数均为质数，则找到答案，输出并结束。
（2）源程序。
#include <stdio.h>
#include <math.h>
int isPrime(int m)
{
int k,i;
k=sqrt(1.0*m);
for (i=2;i<=k;i++)
if (m%i == 0) return 0;
return 1;
}
int main()
{
int n,i,j,flag=0;
scanf("%d",&n);
if (isPrime(n-4)==1)
{
printf("%d %d %d\n",2,2,n-4);
return 0;
}
for (i=3;i<=n/3;i+=2)
{
if (isPrime(i)==0) continue;
for (j=3;j<=n/3;j+=2)
if (isPrime(j) && isPrime(n-i-j))
{
flag=1; break;
}
if (flag==1) break;
}
printf("%d %d %d\n",i,j,n-i-j);
return 0;
}
