b552 - 3.找質數
題目描述
題目給定一個 10 位數的字串，要求從字串的左邊開始，逐步檢查由左邊開始的子字串是否為質數。如果不是質數，則將下一個數字加到子字串的右邊，繼續檢查。如果找到質數，則輸出該質數，並從下一個數字開始重新檢查。最後輸出找到的質數個數以及所有質數。
解題思路
程式碼從輸入的 10 位數字串開始，使用迴圈逐步建立子字串。對於每個子字串，程式碼檢查它是否為質數。如果子字串是質數，則將其儲存在一個陣列中，並將計數器加一。如果子字串不是質數，則將下一個數字加到子字串的右邊，並繼續檢查。質數判斷使用從 2 到子字串平方根的迴圈進行試除法。最後，程式碼輸出找到的質數個數以及所有質數。
複雜度分析
- 時間複雜度: O(N * sqrt(M))，其中 N 是輸入字串的長度 (10)，M 是子字串的最大可能值 (約 10^10)。因為對於每個位置，最壞情況下需要檢查到 sqrt(M) 的數。
- 空間複雜度: O(10)，因為最多儲存 10 個質數。
程式碼
#include <iostream>
#include <cmath>
using namespace std;
int main(){
string a;
while(cin >> a){
long long int ans=0,ansv[11],tmp=0;
bool chat=0;
for(int i=0;i<10;++i,chat=0){
tmp*=10;
tmp+=a[i]-48;
if(tmp==1||tmp==0)
chat=1;
else{
for(int k=2,st=sqrt(tmp);k<=st;++k){
if(tmp%k==0){
chat=1;
break;
}
}
}
if(chat==0){
ansv[ans]=tmp;
++ans;
tmp=0;
}
}
cout << ans << "\n";
for(int i=0;i<ans;++i){
cout << ansv[i] << "\n";
}
cout << "\n";
}
}