解答 - 判斷質數

解法一 - 質數個數法

找出所有因數的同時，一邊紀錄因數的個數。

如果因數個數恰好是2個，則n為質數。

code

#include<iostream>
using namespace std;

int main()
{
    int n;
    int i;
    int counter;

    while( cin >> n )
    {
        counter = 0;

        i = 1;
        while( i <= n )
        {
            if( n%i == 0 )
            {
                counter = counter+1;
            }
            i = i+1;
        }

        if( counter == 2 )
        {
            cout << "Yes" << endl;
        }
        else
        {
            cout << "No" << endl;
        }
    }

    return 0;
}

解法二

假設n不為1。

從 2, 3, 4 ... n-2, n-1 一個一個嘗試能不能整除n，都不能整除的話，n就是質數。

利用變數 ans 紀錄，嘗試的過程中有沒有數字可以整除n。

code

#include<iostream>
using namespace std;

int main()
{
    int n;
    int i;
    int ans;

    while( cin >> n )
    {
        ans = 1;

        i = 2;
        while( i < n )
        {
            if( n%i == 0 )
            {
                ans = 0;
            }
            i = i+1;
        }

        if( ans == 1 )
        {
            cout << "Yes" << endl;
        }
        else
        {
            cout << "No" << endl;
        }
    }

    return 0;
}

自我思考

• 0、1 並不是質數，上面的程式碼會把它們認作質數嗎? 要怎麼修正?

• 變數i 一定要跑過 2, 3, 4...n-2, n-1 嗎? 能不能最後到 n/2 就好?

• 可不可以比上面的方法次數更少?