题解：P12233 [蓝桥杯 2023 国 Java A] X 质数

lczhouzihao · 2025-07-25 19:51:27 · 题解

一串判断质数的函数：

bool p(int n){
    if(n<=1)return false;
    if(n==2)return true;
    if(n%2==0)return false;
    for(int i=3;i*i<=n;i+=2)
        if(n%i==0)return false;
    return true;
}

这里应该没人不会吧。

接着，我们只需枚举每个数，对于每个数，暴力枚举出它删掉 k 个数位后的数，再判断删后的数中有没有质数，如果有，这个数就是 X 质数。

AC code

#include<bits/stdc++.h>
using namespace std;
bool p(int n){
    if(n<=1)return false;
    if(n==2)return true;
    if(n%2==0)return false;
    for(int i=3;i*i<=n;i+=2)
        if(n%i==0)return false;
    return true;
}
bool dfs(string&s,int idx,string&cur){
    if(idx==s.size()){
        if(cur.empty()||(cur[0]=='0'&&cur.size()>1))return false;
        return p(stoi(cur));
    }
    if(dfs(s,idx+1,cur))return true;
    int len=cur.size();
    cur+=s[idx];
    bool res=dfs(s,idx+1,cur);
    cur.resize(len);
    return res;
}
bool c(string&s){
    string cur="";
    return dfs(s,0,cur);
}
int main(){
    int cnt=0;
    for(int i=1;i<=1000000;i++){
        string s=to_string(i);
        if(c(s))cnt++;
    }
    cout<<cnt;
    return 0;
}

最终答案：989457。