自动搬运

查看原文

来自洛谷，原作者为

	lczhouzihao Patience is key in life

搬运于2025-08-24 23:13:53，当前版本为作者最后更新于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$。