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

當然可以!!

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

我們先來看規律吧!

假設一個範圍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;
}