C语言程序设计100例之(11)：求质数

1、C 语言程序设计100 例之（ 11）：求质数例 11求质数问题描述质数是指除了有1 和自身作为约数外，不再有其他约数的数。比如：3、5、 7 是质数。而不是质数，因为它还有约数3。编写程序求给定区间中的所有质数。输入格式两个整数 a 和 b，其中 1 a b10000输出格式输出给定范围的所有质数，输出时每个质数占5 列，每行输出10 个质数。输入样例9100200输出样例101103107109113127131137139 149151157163167173179181191193 197199（1）编程思路判断一个数m 是否为质数的方法是：用2sqrt(m) 中的每一个整数i 去除

2、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;求 ab 之间的所有质数，写成一个循环，在循环中调用函数 isPrime 判断每个整数 i 是否为质数，若是，则计数并输出。（2）源程序。#include #include int isPrime(int m)int i;if (m=1) return 0;for (i=2;i=sqrt(1.0*m);i+)if

3、 (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;习题 1111-1回文质数问题描述我国古代有一种回文诗，倒念顺念都有意思，例如“人过大佛寺” ，倒读起来便是“寺佛大过人”。还有经典的对联“客上天然居，居然天上客”等。在自然数中，如果一个数从左向右读或是从右向左读完全一致，这样的自然数称为回文数。编写一个程序，找出N 之内的所有

4、回文质数。所谓回文质数就是一个数即是一个质数又是一个回文数，例如，151 是回文质数。输入格式一个整数 N，其中 1 N1000000输出格式输出 N 以内的所有回文质数，输出时每个回文质数占5 列，每行输出 10 个回文质数。输入样例10000输出样例235711101131151181191313 3533733837277577877979199291）编程思路。将判断一个数是否为质数和是否为回文数分别写成一个函数。函数函数int isPrime(int m);int isPalm(int m);判断数判断数m 是否为质数， m 是质数，函数返回值为1，否则为0。m 是否为回文数，m 是

5、回文数，函数返回值为1，否则为0。（ 2）源程序。#include #include int isPrime(int m)int i;if (m=1) return 0;for (i=2;i0)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(%6d,i);if (cnt%10=0) printf(n);return 0;从程序运行结果可以看出，回文质数除了 11 以外，所有回文质数

6、的位数都是奇数。这是因为， 如果一个回文数的位数是偶数， 则它的奇数位上的数字之和与偶数位上的数字之和必然相等。根据数的整除性原理，这样的数肯定能被 11 整除。因此，回文质数的位数绝不可能是偶数（除 11 外）。11-2第 N 个质数问题描述质数就是不能再进行等分的整数。比如：7， 11 是质数。而9 不是质数，因为它可以平分为3 等份。一般认为最小的质数是2，接着是3， 5， .设“ 2” 是第一个质数， “ 3” 是第二个质数，依此类推。问第输入格式N 个质数是多少？一个整数 N，其中 1 N1000000输出格式一个整数，它是第N 个质数。输入样例10输出样例29（ 1）编程思路。先处

7、理 n=1，输出 2 的特殊情况。因为，2 之后的所有质数均为奇数。记当前质数个数 cnt=1（ 2 是第 1 个质数），从 i=3 开始，顺序判断当前奇数是否为质数，若是质数则 cnt+，若 cnt=n，则当前奇数为第 n 个质数，结束循环查找并输出结果。（ 2）源程序。#include #include 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) p

8、rintf(2n);elsecnt=1; i=3;while(1)if (isPrime(i) cnt+;if(cnt=n) break;i+=2;printf(%dn,i);return 0;11-3哥德巴赫猜想（升级版）题目描述1742 年 6 月 7 日哥德巴赫写信给当时的大数学家欧拉，正式提出了以下的猜想：任何一个大于 9 的奇数都可以表示成3 个质数之和。质数是指除了如 2 和 11 都是质数，而6 不是质数，因为6 除了约数别说明的是1 不是质数。1 和本身之外没有其他约数的数，1 和 6 之外还有约数2 和 3。需要特这就是哥德巴赫猜想。欧拉在回信中说，他相信这个猜想是正确的，但

9、他不能证明。从此，这道数学难题引起了几乎所有数学家的注意。 哥德巴赫猜想由此成为数学皇冠上一颗可望不可及的“明珠” 。现在请你编一个程序验证哥德巴赫猜想。输入格式仅有一行，包含一个正奇数n，其中 9n20000输出格式仅有一行， 输出 3 个质数， 这 3 个质数之和等于输入的奇数。 相邻两个质数之间用一个空格隔开，最后一个质数后面没有空格。如果表示方法不唯一，请输出第一个质数最小的方案，如果第一个质数最小的方案不唯一， 请输出第一个质数最小的同时， 第二个质数最小的方案。输入样例2009输出样例3 3 2003（ 1）编程思路。对输入的正奇数n，先判断其和是否含有质数2，只有一种可能2+2+

10、（ n-4），若 n-4 是质数，则直接输出结果，结束。如果 n 的和值中不包含质数2，则只能分解为3 个奇数之和。不妨设n=i+j+(n-i-j) 。用一个二重循环寻找答案。 外循环 i 为 3n/3 之间的所有奇数， 内循环 j 为 in/3 之间的所有奇数，在内循环中调用函数isPrime 判断，若i、 j、 n-i-j 三个数均为质数，则找到答案，输出并结束。（ 2）源程序。#include #include 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 %dn,2,2,n-4);return 0;for (i=