数学

来源于@Hywhh

快去早读

看到此题，初步认为不存在a，即$a \to \infty$。

下面的程序输入a，输出最小的进行a次操作后得到质数的数。

#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$次操作后得到质数。

不过为什么刚刚上传图片的时候forum.eduzhixin.com显示“色情”？

将第12行的<ceil改为<=floor之后，得到了新的答案。

与原来答案大体相同，但a=3时得到了74，而非50。

大概算了90分钟吧，a=20的结果是112745722。