40% TLE 的解决方法

基础解题方法
普遍我的做法：
遍历[2,n]之间的数
再对每一个数的子数进行素数判断
存储 计数 输出

#include <bits/stdc++.h>
usinging namespace std;

const unsigned MAX=1e7+5;
unsigned m=0,cnt=0,ans[MAX],len;
string n;

bool isp(unsigned x){
	if (x<=1) return false;
	for (int i=2;i*i<=x;i++){
		if (x%i == 0) return false;
	}
	return true;
}

bool ispp(unsigned x){
	unsigned s[20],idx=0,k;
	
	while (x){
		s[idx++] = x%10;
		x /= 10;
	}
	
	for (int i=0;i<idx/2;i++){
		swap(s[i],s[idx-i-1]);
	}
	
	for (int i=1;i<=idx;i++){
		for (int j=0;j<idx-i+1;j++){
			k=0;
			for (int d=0;d<i;d++){
				k *= 10;
				k += s[j+d];
			}
			if (!isp(k)) return false;
		}
	}
	
	return true;
}


int main(){
	cin>>n;
	
	len = n.size();
	for (int i=0;i<len;i++) m += pow(10,i)*(n[len-i-1]-'0');
	
	for (int i=2;i<=m;i++){
		if (ispp(i)) ans[cnt++] = i;
	}
	
	cout<<cnt<<endl;
	for (int i=0;i<cnt;i++){
		cout<<ans[i]<<endl;
	}
	
	
	return 0;
}

时间复杂度：O(n^3.5)
在60%的数据是可以接受的
但仍能进行优化

使用欧拉筛提前计算出范围内的素数
n较小判断时直接查询标志数组
时间复杂度：O(n^3)
n较大时需要至质数数组查找
使用二分查找
时间复杂度：O(n^3 * log_2(n))

此处不贴代码了，留给读者自行编写(懒)
但你会发现即使做了这些优化仍不能做到AC
因为 n<1e18 明摆着就是不能正常写

因此需要运用到一些简单的数论知识
超级素数 的定义意味着数字本身必须是素数。
显然不存在n>373的这样的素数。
证明：
From Jean-Marc Falcoz , Jan 11 2009:
"""
This is correct.
There can't be any more terms, because they must necessarily be of the form
23737373733737... but the substring 237 is composite
or 273737373... but 273 is composite
or 5373737373... but 537 is composite
or 5737373737... but 573 is composite
or 37373737373... but 3737 is composite
or 7373737373... but 737 is composite
No other form is possible, otherwise, if the digit 2 or 5 is anywhere inside or at the end of the number, one substring-number is even or divisible by 5, and furthermore, there can't be twin digits, because one substring-number would then be divisible by 11.
Obviously, the digits 0, 1, 4, 6, 8, 9 can't appear anywhere in a term of the sequence.
"""
详见 OEIS A085823

所以只需要加入个特判就能AC了

#include <bits/stdc++.h>
usinging namespace std;

const unsigned MAX=1e7+5;
unsigned m=0,cnt=0,ans[MAX],len;
string n;

bool isp(unsigned x){
	if (x<=1) return false;
	for (int i=2;i*i<=x;i++){
		if (x%i == 0) return false;
	}
	return true;
}

bool ispp(unsigned x){
	unsigned s[20],idx=0,k;
	
	while (x){
		s[idx++] = x%10;
		x /= 10;
	}
	
	for (int i=0;i<idx/2;i++){
		swap(s[i],s[idx-i-1]);
	}
	
	for (int i=1;i<=idx;i++){
		for (int j=0;j<idx-i+1;j++){
			k=0;
			for (int d=0;d<i;d++){
				k *= 10;
				k += s[j+d];
			}
			if (!isp(k)) return false;
		}
	}
	
	return true;
}


int main(){
	cin>>n;
	if (n.size()>4) n = "373";
	
	len = n.size();
	for (int i=0;i<len;i++) m += pow(10,i)*(n[len-i-1]-'0');
	
	for (int i=2;i<=m;i++){
		if (ispp(i)) ans[cnt++] = i;
	}
	
	cout<<cnt<<endl;
	for (int i=0;i<cnt;i++){
		cout<<ans[i]<<endl;
	}
	
	
	return 0;
}

时间复杂度：O(n^3.5) (n<=373)
也可以用上述做法优化
时间复杂度：O(n^3) (n<=373)
此处仍不贴代码，留给读者自行编写(懒)
对于n<=373来说 O(n^3.5) 已经足够

悄悄告诉你 这题答案量小 打表 O(1) 哦