用C++找出某範圍中的質數

真的能用程式來找質數嗎?

當然可以!!

只要摸清楚質數的規律,就能利用迴圈來進行運算

我們先來看規律吧!

假設一個範圍x為1~15

我們可知範圍x中的質數為2 3 5 7 11 13

你有發現什麼嗎?

沒錯!這六個質數中,只有2是雙數,其它的都是奇數

原因就是所有偶數都能被2整除,而2卻不能被「除了自己和1之外」的數給整除

所以我們知道,2是質數中唯一的雙數

由於2算是一個特例,所以先不要考慮它,我們考慮3 5 7 11 13就好

如果你要用迴圈找出這5個數,你會怎麼找

當然,你需要一開始的範圍值1~15,將這範圍值當作是外迴圈,利用內迴圈進行判斷

問題又來了,要怎麼判斷呢?

我們可以利用「已知」,來找出一個公式

假設外迴圈(此迴圈計數值範圍為1~15)目前的計數值是3,我們知道若某數除以某質數可以整除的話,那該數就不是質數

某數除以「某質數」,這個某質數的範圍必小於某數,因為大於就更不可能整除了,沒有意義

也就是說「某質數」小於「某數」,又2是所有質數中最小的數,所以這個某質數又會大於等於2

利用這點,我們可以利用迴圈一個一個快速判別

至於如何判別,繼續看下去吧

當外迴圈的計數值為1,內迴圈的計數值為2,外迴圈的計數值小於內迴圈的計數值(1<2),依照剛才上面的推論「某質數」要小於「某數」,則內迴圈不能被執行

當外迴圈的計數值為2,內迴圈的計數值為2,外迴圈的計數值等於內迴圈的計數值(2=2),依照剛才上面的推論「某質數」要小於「某數」,但2是例外,要分開來判斷,所以就算這個條件不成立,但2還算是質數

我們看看3 5 7 11 13吧

當外迴圈的計數值為3,內迴圈的計數值為2,則外迴圈的計數值等於內迴圈的計數值加一,已知3是質數

當外迴圈的計數值為3,內迴圈的計數值為3,則外迴圈的計數值除以內迴圈的計數值後的餘數等於0

當外迴圈的計數值為4,內迴圈的計數值為2,則外迴圈的計數值除以內迴圈的計數值之餘數等於0,又因4是偶數,所以不是質數,可不用繼續考慮

當外迴圈的計數值為5,內迴圈的計數值為2,則外迴圈的計數值等於內迴圈的計數值加三

當外迴圈的計數值為5,內迴圈的計數值為3,則外迴圈的計數值等於內迴圈的計數值加二

當外迴圈的計數值為5,內迴圈的計數值為4,則外迴圈的計數值等於內迴圈的計數值加一,已知5是質數

當外迴圈的計數值為5,內迴圈的計數值為5,則外迴圈的計數值除以內迴圈的計數值後的餘數等於0

當外迴圈的計數值為6,內迴圈的計數值為2,則外迴圈的計數值除以內迴圈的計數值之餘數等於0,又因6是偶數,所以不是質數,可不用繼續考慮

當外迴圈的計數值為7,內迴圈的計數值為2,則外迴圈的計數值等於內迴圈的計數值加五

當外迴圈的計數值為7,內迴圈的計數值為3,則外迴圈的計數值等於內迴圈的計數值加四

當外迴圈的計數值為7,內迴圈的計數值為4,則外迴圈的計數值等於內迴圈的計數值加三

當外迴圈的計數值為7,內迴圈的計數值為5,則外迴圈的計數值等於內迴圈的計數值加二

當外迴圈的計數值為7,內迴圈的計數值為6,則外迴圈的計數值等於內迴圈的計數值加一,已知7是質數

當外迴圈的計數值為7,內迴圈的計數值為7,則外迴圈的計數值除以內迴圈的計數值後的餘數等於0

當外迴圈的計數值為8,內迴圈的計數值為2,則外迴圈的計數值除以內迴圈的計數值之餘數等於0,又因8是偶數,所以不是質數,可不用繼續考慮

當外迴圈的計數值為9,內迴圈的計數值為2,則外迴圈的計數值等於內迴圈的計數值加七

當外迴圈的計數值為9,內迴圈的計數值為3,則外迴圈的計數值除以內迴圈的計數值後的餘數等於0,又因9絕對不是質數(因為它可被3整除),可不用繼續考慮

當外迴圈的計數值為10,內迴圈的計數值為2,則外迴圈的計數值除以內迴圈的計數值之餘數等於0,又因10是偶數,所以不是質數,可不用繼續考慮

當外迴圈的計數值為11,內迴圈的計數值為2,則外迴圈的計數值等於內迴圈的計數值加九

當外迴圈的計數值為11,內迴圈的計數值為3,則外迴圈的計數值等於內迴圈的計數值加八

當外迴圈的計數值為11,內迴圈的計數值為4,則外迴圈的計數值等於內迴圈的計數值加七

當外迴圈的計數值為11,內迴圈的計數值為5,則外迴圈的計數值等於內迴圈的計數值加六

當外迴圈的計數值為11,內迴圈的計數值為6,則外迴圈的計數值等於內迴圈的計數值加五

當外迴圈的計數值為11,內迴圈的計數值為7,則外迴圈的計數值等於內迴圈的計數值加四

當外迴圈的計數值為11,內迴圈的計數值為8,則外迴圈的計數值等於內迴圈的計數值加三

當外迴圈的計數值為11,內迴圈的計數值為9,則外迴圈的計數值等於內迴圈的計數值加二

當外迴圈的計數值為11,內迴圈的計數值為10,則外迴圈的計數值等於內迴圈的計數值加一,已知7是質數

當外迴圈的計數值為11,內迴圈的計數值為11,則外迴圈的計數值除以內迴圈的計數值後的餘數等於0

到這裡應該就能看出來規律了吧!凡是只要是質數,其某次外迴圈的計數值等於內迴圈的計數值加一,且下一次外迴圈的計數值除以內迴圈的計數值後的餘數等於0

凡只要不是質數,其某次外迴圈的計數值除以內迴圈的計數值後的餘數等於0

這是巧合嗎? 不,你再看看吧

當外迴圈的計數值為12,內迴圈的計數值為2,則外迴圈的計數值除以內迴圈的計數值後的餘數等於0,又因12是偶數,所以不是質數,可不用繼續考慮

當外迴圈的計數值為13,內迴圈的計數值為2,則外迴圈的計數值等於內迴圈的計數值加十一

當外迴圈的計數值為13,內迴圈的計數值為3,則外迴圈的計數值等於內迴圈的計數值加十

當外迴圈的計數值為13,內迴圈的計數值為4,則外迴圈的計數值等於內迴圈的計數值加九

當外迴圈的計數值為13,內迴圈的計數值為5,則外迴圈的計數值等於內迴圈的計數值加八

當外迴圈的計數值為13,內迴圈的計數值為6,則外迴圈的計數值等於內迴圈的計數值加七

當外迴圈的計數值為13,內迴圈的計數值為7,則外迴圈的計數值等於內迴圈的計數值加六

當外迴圈的計數值為13,內迴圈的計數值為8,則外迴圈的計數值等於內迴圈的計數值加五

當外迴圈的計數值為13,內迴圈的計數值為9,則外迴圈的計數值等於內迴圈的計數值加四

當外迴圈的計數值為13,內迴圈的計數值為10,則外迴圈的計數值等於內迴圈的計數值加三

當外迴圈的計數值為13,內迴圈的計數值為11,則外迴圈的計數值等於內迴圈的計數值加二

當外迴圈的計數值為13,內迴圈的計數值為12,則外迴圈的計數值等於內迴圈的計數值加一,已知13是質數

當外迴圈的計數值為13,內迴圈的計數值為13,則外迴圈的計數值除以內迴圈的計數值後的餘數等於0

以上數據,證實了「凡是只要是質數,其某次外迴圈的計數值等於內迴圈的計數值加一,且下一次外迴圈的計數值除以內迴圈的計數值後的餘數等於0」和「凡只要不是質數,其某次外迴圈的計數值除以內迴圈的計數值後的餘數等於0」這兩個推論,因此我們可得公式:

質數:某次外迴圈的計數值等於內迴圈的計數值加一

非質數:某次外迴圈的計數值除以內迴圈的計數值後的餘數等於0

設外迴圈的計數變數為x,內迴圈的計數變數為y

質數:(x==y+1)

非質數:(x%y==0)

找到公式後,開始撰寫程式碼吧!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream> //只需用到這個函式庫
using namespace std;
 
int main()
{
int a,b,x,y; //a、b為範圍值(前者、後者);x為外迴圈;y為內迴圈
while(true)  //無窮迴圈,目的要讓使用者連續輸入資料
{
cout << "請輸入二整數,其將成為一個範圍,本程式會找出範圍中的質數:";
cin >> a >> b ;
 
if(b>a&&b>=2) //若b>a(後者大於前者),且b要大於等於2,因為2是最小的質數,若b小於2,那就找不到質數了
{
cout << a << "~" << b << "質數有:"; //提示顯示出來的數字是什麼
if (a<=2) //如果a小於2的話,那範圍內就有包含2,所以有質數2
cout << "2" << " ";
for(x=a;x<=b;x++) //x外迴圈,x範圍為a~b
{
for(y=2;y<=x;y++) //y內迴圈
{
if(x%y==0) //判斷非質數和質數,若條件式為真,則跳出迴圈
break;  //跳出y內迴圈
else if (x==y+1) //判斷是否為質數
cout << x << " "; //輸出x值,就是質數
}
}
}
else if (a>b&&a>=2) //若a>b(前者大於後者),則下面都跟上面寫法相反,a要改成b,b要改成a,其它不去更動
{
cout << b << "~" << a << "質數有:";
if (b<=2)
cout << "2" << " ";
for(x=b;x<=a;x++)
{
for(y=2;y<=x;y++)
{
if(x%y==0)
break;
else if (x==y+1)
cout << x << " ";
}
}
}
else //使用者可能輸入二相等數,或是範圍值內完全沒有質數
cout << "輸入範圍有誤,可能是二數相等,又可能是因為範圍值內完全沒有質數";
cout << endl ; //換行,然後跳到while迴圈敘述最上端,繼續要求使用者輸入資料
}
system ("pause");
return 0;
}
文章分類:C & C++|標籤:,

迴響已關閉