例11 求質數 問題描述 質數是指除了有1和自身作為約數外，不再有其他約數的數。比如：3、5、7是質數。而9不是質數，因為它還有約數3。 編寫程式求給定區間中的所有質數。 輸入格式 兩個整數a和b，其中1≤a≤b≤100000。 輸出格式 輸出給定範圍的所有質數，輸出時每個質數占5列，每行輸出10個 ...
例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;
}
