ZeroJudge 解題筆記：e795. p2.質數日

作者：王一哲
日期：2025年1月30日



ZeroJudge 題目連結：e795. p2.質數日

解題想法

因為測資範圍不太，在判斷數字 $n$ 是否為質數時，只要用 for 迴圈從 2 開始測試到 $\sqrt{n}$，任何一個數可以整除 $n$ 則 $n$ 不是質數，不需要用太複雜的作法。

Python 程式碼

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

def test(s):  # 輸入日期 s，字串格式，測試其是否為質數日
    while len(s) >= 1 and int(s) >= 2:  # 如果 s 長度大於等於 1，轉成整數大於等於 2，繼續執行
        date = int(s)  # s 轉成 int
        imax = int(date**0.5)  # 測試的上限，date 開根號
        for i in range(2, imax+1):  # 依序測試 2 ~ imax 是否能整除 date
            if date%i == 0: return False  # 如果能整除，回傳 Fasle 並跳出函式
        s = s[1:]  # 刪除 s 開頭的字元
    return True  # 如果能跑完 while 迴圈，s 是質數日，回傳 True

D = int(input())  # D 個日期
for _ in range(D):  # 測試 D 次
    N = input().strip()  # 讀取日期 N
    print(N, end=" ")  # 印出答案
    print("is" if test(N) else "isn't", end="")
    print(" a Prime Day!")

C++ 程式碼

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

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

bool test(string s) {  // 輸入日期 s，字串格式，測試其是否為質數日
    while(s.size() >= 1 && stoi(s) >= 2) {  // 如果 s 長度大於等於 1，轉成整數大於等於 2，繼續執行
        int date = stoi(s);  // s 轉成 int
        int imax = (int)sqrt(date);  // 測試的上限，date 開根號
        for(int i=2; i<=imax; i++) {  // 依序測試 2 ~ imax 是否能整除 date
            if (date%i == 0) return false;  // 如果能整除，回傳 Fasle 並跳出函式
        }
        s = s.substr(1);  // 刪除 s 開頭的字元
    }
    return true;  // 如果能跑完 while 迴圈，s 是質數日，回傳 True
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int D; cin >> D;  // D 個日期
    for(int i=0; i<D; i++) {  // 測試 D 次
        string N; cin >> N;  // 讀取日期 N
        cout << N << " " << (test(N) ? "is" : "isn't") << " a Prime Day!\n";  // 印出答案
    }
    return 0;
}