【題解】ZeroJudge e795: p2.質數日

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=e795
【解題想法】題目保證不會有非日期表示之輸入,只要判斷是否為質數。

#include <iostream>
#include <cmath>
using namespace std;
const int maxn = 30000000;
bool p[maxn];

int main() {
    // 建立指數表
    p[0] = p[1] = 1;
    for (int i=2; i<maxn; i++){
        if (!p[i]){
            for (int j=2*i; j<maxn; j+=i){
                p[j] = 1;
            }
        }
    }
    int D;
    cin >> D;
    while (D--){
        int d;
        cin >> d;
        bool flag = true;
        for (int i=8; i>=1; i--){
            int tmp=d, b = 1;
            for (int j=1; j<=i; j++) b *= 10;
            tmp %= b;
            if (p[tmp]){
                flag = false;
                break;
            }
        }
        if (flag) cout << d << " is a Prime Day!\n";
        else cout << d << " isn't a Prime Day!\n";
    }
    return 0;
}

Python code (credit: Amy Chou)

def isPrime(x):
    for i in range(2, int(pow(x, 0.5))):
        if x % i == 0:
            return False
    return True

D = int(input())
for _ in range(D):
    d = int(input())
    flag = True
    for i in range(8, 0, -1):
        tmp = d % pow(10, i)
        if not isPrime(tmp):
            flag = False
            break
    if flag:
        print(f"{d} is a Prime Day!")
    else:
        print(f"{d} isn't a Prime Day!")
分享本文 Share with friends