B4158 [BCSP-X 2024 12 月小學高年級組] 質數補全 - 洛谷

思路1:線性篩,字符串匹配,枚舉

質數篩選

要解決這個問題，首先得找出指定范圍內（這里是 1 到 10000000）的所有質數。常用的質數篩選算法有埃拉托斯特尼篩法（埃氏篩）和歐拉篩法（線性篩），本題建議采用的是歐拉篩法，其時間復雜度為?O(n)，具體步驟如下：

• 初始化一個布爾類型的數組?vis，用于標記每個數是否為質數。把?vis[0]?和?vis[1]?標記為非質數（因為 0 和 1 不是質數）。
• 從 2 開始遍歷到 10000000，對于每個數?i：
  • 若?vis[i]?為?false，說明?i?是質數，將其存儲到質數數組（第一段代碼是?prime?數組，第二段代碼是?primes?向量）中。
  • 遍歷已找到的質數，將?i?與這些質數的乘積標記為非質數。若?i?能被當前質數整除，就停止內層循環，這能保證每個合數只被其最小質因數篩去一次，從而實現線性時間復雜度。

字符串匹配判斷

在找出所有質數后，需要判斷輸入的帶有?*?通配符的字符串是否能與某個質數匹配。可以定義一個判斷函數具體步驟如下：

• 首先檢查兩個字符串的長度是否相同，若不同則直接返回?false。
• 接著遍歷兩個字符串的每個字符：
  • 若對應位置的字符相同，繼續檢查下一個字符。
  • 若輸入字符串中對應位置的字符是?*，表示該位置可以匹配任意字符，繼續檢查下一個字符。
  • 若對應位置的字符既不相同，輸入字符串中對應位置的字符也不是?*，則返回?false。
• 若遍歷完所有字符都沒有返回?false，則返回?true。

代碼：
?

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
bool vis[10000005];
int n;
vector<int> primes;void euler(){vis[0]=vis[1]=true;for(int i=2;i<=10000000;++i){if(!vis[i])primes.push_back(i);for(int j=0;j<primes.size()&&i*primes[j]<=10000000;++j){vis[i*primes[j]]=true;if(i%primes[j] == 0) break;}}
}bool check(string a,string b){if(a.size()!=b.size())return false;for(int i=0;i<a.size();++i){if(a[i]!=b[i]&&b[i]!='*')return false;}return true;
}int main(){int n;cin>>n;euler();while(n--){string s;cin>>s;bool flag = false;for(auto i:primes){if(check(to_string(i),s)){cout<<i<<endl;flag = true;break;}}if (!flag) cout<<"-1"<<endl;}return 0;
}