例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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/63328.html
標籤：C
上一篇：第一周、學習嵌入式
下一篇：HttpClient