e795 - p2.質數日
題目描述
題目要求判斷給定的日期是否為「質數日」。一個日期被稱為質數日，如果將日期表示為一個整數，以及從該整數中提取出的所有可能的子字串（從左到右），都為質數。
解題思路
程式碼首先定義了一個 isPrime 函數，用於判斷一個整數是否為質數。主函數讀取多組測試案例，對於每個案例，將輸入的日期字串轉換為整數，然後從日期字串的左側開始，提取所有可能的子字串，並判斷這些子字串是否都是質數。如果所有子字串都是質數，則輸出「N is a Prime Day!」，否則輸出「N isn’t a Prime Day!」。
複雜度分析
- 時間複雜度: O(D * 8 * sqrt(10^8))，其中 D 是測試案例的數量。對於每個日期，需要提取最多 8 個子字串，並且對於每個子字串，需要進行質數判斷，質數判斷的時間複雜度為 O(sqrt(n))，n 最大為 10^8。
- 空間複雜度: O(1)，程式碼只使用了常數級別的額外空間。
程式碼
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
string s;
bool isPrime(int n){
int k=sqrt(n);
for(int i=2;i<=k;i++)
if(n%i==0)return 0;
return 1;
}
int main() {
ios_base::sync_with_stdio(false);cin.tie(NULL);
int t;
cin>>t;
while(t--){
cin>>s;
cout << s;
bool flag=false;
for(int i=0;i<8;i++){
int n=0;
for(int ii=i;ii<8;ii++){
n*=10;
n+=s[ii]-'0';
}
if(isPrime(n)==0){
flag=1;
break;
}
}
if(flag)cout<<" isn't a Prime Day! \n";
else cout<<" is a Prime Day! \n";
}
}