CF1861A Prime Deletion

One_JuRuo · 2023-09-01 23:50:52 · 个人记录

思路

诈骗题，看着很难，其实是一道大水题。

常识告诉我们，对于一个两位数，首位无论是几，都一定存在质数。

所以我们就把输入的字符串第一位作为质数的第一位，遍历字符串，找到刚好与第一位组成质数就行了。

AC code

#include<bits/stdc++.h>
using namespace std;
int T,su[105],pri[105],cnt;
char ch[10];
inline void init()
{
    for(int i=2;i<=100;++i)
    {
        if(!su[i]) pri[++cnt]=i;
        for(int j=1;j<=cnt&&pri[j]*i<=100;++j)
        {
            su[i*pri[j]]=1;
            if(i%pri[j]==0) break;
        }
    }
}
int main()
{
    init();
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",ch+1);
        int t=ch[1]-'0';
        for(int i=2;i<=9;++i) if(!su[t*10+ch[i]-'0']){printf("%c%c\n",ch[1],ch[i]);break;}
    }
    return 0;
}
 

优化

这么做其实不算很优，可以提前用个数组存好每个数开头的某一个质数，然后字符串第一位是几，就输出第几个数组的数字。

int ans[10]={0,13,23,37,41,53,61,73,89,97};

然后输入输出就是：

scanf("%s",ch);
printf("%d\n",ans[ch[0]-'0']);