ZeroJudge 解題筆記：n362. 質數遊戲 (Primes)

作者：王一哲
日期：2025年6月7日


ZeroJudge 題目連結：n362. 質數遊戲 (Primes)

解題想法

先寫一個函式 prime 判斷輸入的數字是否為質數；再寫另一個函式 solve，判斷輸入的數字是否可以由兩個質數相除。由於測資不太，如果輸入的數字是 $n$，這兩個函式都只要測試 $2$ 到 $\sqrt{n}$ 即可。

Python 程式碼

使用時間約為 34 ms，記憶體約為 3.3 MB，通過測試。

import sys

def prime(n):  # 檢查是否為質數
    for i in range(2, int(n**0.5)+1):  # 測試 2 ~ sqrt(n)
        if n%i == 0: return False  # 不是質數
    return True  # 是質數

def solve(n):  # 自訂函式求解
    for a in range(2, int(n**0.5)+1):  # 測試可能的因數 2 ~ sqrt(n)
        if n%a == 0:  # 如果 a 是因數
            b = n//a  # 另一個數
            if prime(a) and prime(b):  # 如果 a, b 都是質數
                print(a, b); return  # 印出 a, b，跳出函式
    print(0, 0)  # 印出 0, 0

for line in sys.stdin:
    solve(int(line))

C++ 程式碼

使用時間約為 2 ms，記憶體約為 144 kB，通過測試。

#include <cstdio>
#include <cmath>
using namespace std;

bool prime(int n) {  // 檢查是否為質數
    for(int i=2; i<=int(sqrt(n)); i++) {  // 測試 2 ~ sqrt(n)
        if (n%i == 0) return false;  // 不是質數
    }
    return true;  // 是質數
}

void solve(int n) {  // 自訂函式求解
    for(int a=2; a<=int(sqrt(n)); a++) {  // 測試可能的因數 2 ~ sqrt(n)
        if (n%a == 0) {  // 如果 a 是因數
            int b = n/a;  // 另一個數
            if (prime(a) && prime(b)) {  // 如果 a, b 都是質數
                printf("%d %d\n", a, b);  // 印出 a, b
                return;  // 跳出函式
            }
        }
    }
    printf("0 0\n");  // 印出 0, 0
}

int main() {
    int n;
    while(scanf("%d", &n) != EOF) solve(n);
    return 0;
}