ZeroJudge N362: 質數遊戲 (Primes)

阿軒是個國中老師，他最近剛教到質因數分解這個單元，為了讓學生們練習，他會提出一個數字 N，請同學回答這個數字是不是由兩個質數的乘積，如果是則要說出是由哪兩個質數相乘。

請你撰寫一個程式來產生正確解答。

範例測資

範例輸入範例輸出
輸入僅有一列，包含一個數字 N (2 ≤ N ≤ 2 × 109)。若 N 是兩個質數 A 與 B 的乘積，輸出兩個質數 A 與 B (A ≤ B)，兩數之間以一個空格分開。若 N 不是兩個質數的乘積，輸出「0 0」。
142 7
630 0
917747257 3571

解題思路

判斷 N 的因數，For迴圈只需從 2 跑到 sqrt(N)+1 即可。如果有因數的話就判斷該因數是否為質數，判斷質數也是確認 2 到 sqrt(因數)+1 是否有其他因數。還要判斷 N/因數 這個數字是否為質數，如果是的話就可以輸出兩個數字並 break 迴圈。

範例程式碼－ZeroJudge N362: 質數遊戲 (Primes)

#include <iostream>
#include <math.h>
using namespace std;

bool isPrime(int N)
{
    for (int i = 2; i<int(sqrt(N))+1; i++)
    {
        if (N % i == 0) return false;
    }
    return true;
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    bool ok = false;
    for (int i = 2; i<int(sqrt(N))+1; i++)
    {
        if (N % i == 0 && isPrime(i) && isPrime(N / i))
        {
            ok = true;
            cout << i << " " << N/i << "\n";
            break;
        }
    }
    if (!ok) cout << "0 0\n";
}

//ZeroJudge N362
//Dr. SeanXD
標籤

相關文章

發佈留言