#include <cstdio>
#include <cmath>
#pragma GCC optimize('Ofast')
int max(int a,int b) {
return a>b?a:b;
}
bool prime(int n) { //判断n是否为质数
if (n == 2 || n == 3) return true;
if (n % 6 == 1 || n % 6 == 5) {
for (register int i=2;i<ceil(sqrt(n));++i)
if (n % i == 0) return false;
return true;
} else return false;
}
inline int Maxprime(int n,int t=2) { //求n的不比t小的最大质因子
if (prime(n)) return n;
for (int i=t;i<=floor(sqrt(n));++i) {
if (n % i == 0) if (prime(i)) {
return max(i,Maxprime(n/i,i));
}
} return 2;
}
inline int play(int n,int s=0) {
if (prime(n)) {
return s;
} else {
int m=Maxprime(n);
return play(m*10+m%10,s+1);
}
}
signed main() {
int a=1;
while (a>0) {
scanf("%d",&a);
for (register int i=2;;++i) {
if (play(i) == a) {
printf("%d\n",i);
break;
}
}
} return 0;
}
运行。
从a=1算到a=19,前面都是秒出答案,注意这里a=5算出4是没有问题的,操作过程4->22->111->377->299->233。a=16卡了2秒算出669454,a=17卡了十几秒算出2059306,a=18……大概1分钟吧,算出9290338。a=19可是算了7-8分钟,终于算出16831162。后面不想算了,再大一点就要算很久。不过虽然要算很久,看这个趋势,应该都是可以算得出来的,不至于没有结果。可以认为对于$\forall a \exist p \in R \ni p$进行$a$次操作后得到质数。