不玩筛不爽。

以下记 $r-l+1$ 为 $n$。

Level.1：菜鸟级别暴力——枚举

直接对于每个数进行枚举是否是幸运素数。

#include<bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f
using namespace std;
int l,r;
bool prime(int x){
	if(x<=1)return 0;
	for(int i=2;i*i<=x;i++)
		if(!(x%i))return 0;
	return 1;
}
bool rz(int x){
	while(x){
		if(!prime(x))return 0;
		x/=10;
	}
	return 1;
}
signed main(){
	cin>>l>>r;
	for(int i=l;i<=r;i++)
		if(rz(i))cout<<i<<"\n";
	return 0;
}

时间复杂度 $O(n\sqrt{n})$，可以通过单组 $n=10^5$ 时的数据。但是遇到 $n=10^6$ 以上或者多组数据就歇菜了，适合菜鸟使用。

Level.2：中等级别暴力——质数筛

先筛出质数，然后用上面的方法。

#include<bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f
using namespace std;
int l,r,p[30001];
bool rz(int x){
	while(x){
		if(!p[x])return 0;
		x/=10;
	}
	return 1;
}
signed main(){
	for(int i=2;i<=12000;i++)
		p[i]=1;
	for(int i=2;i<=12000;i++){
		if(p[i]){
			for(int j=2;i*j<=12000;j++)
				p[i*j]=0;
		}
	}
	cin>>l>>r;
	for(int i=l;i<=r;i++)
		if(rz(i))cout<<i<<"\n";
	return 0;
}

质数筛就是对于每一个确定下来的质数，枚举它们的倍数进行删除（本身除外）。最后剩下的就是质数。

时间复杂度为 $O(n\log_{10} n)$，已经比较优秀，可以通过 $n=10^6$ 时的数据，而且可以应付多组（$10\sim30$ 组）的数据。

Level.3：狂筛级别暴力——质数筛+幸运素数筛（玄学）

无法描述。先进行质数筛，然后将 $2,3,5,7$ 标记为幸运素数；然后对于每个幸运素数，若它的十倍加上某一个一位数为质数，则将它的十倍加上某一个一位数标记为幸运素数。

#include<bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f
using namespace std;
int l,r,p[30001],f[300001];
signed main(){
	for(int i=2;i<=12000;i++)
		p[i]=1;
	for(int i=2;i<=12000;i++){
		if(p[i]){
			for(int j=2;i*j<=12000;j++)
				p[i*j]=0;
		}
	}
	f[2]=f[3]=f[5]=f[7]=1;
	for(int i=2;i<=12000;i++){
		if(f[i]){
			for(int j=1;j<=9;j++)
				if(p[i*10+j])f[i*10+j]=1;
		}
	}
	cin>>l>>r;
	for(int i=l;i<=r;i++)
		if(f[i])cout<<i<<"\n";
	return 0;
}

时间复杂度为 $O(n)$，可以轻松拿捏 $n=10^6$ 时的数据，并且可以通过 $100$ 组左右的数据，不超时。

Level.114514：圆满级别暴力——不筛了（更加玄学）

和 Level.3 很像，就是进行了空间的优化。

#include<bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f
using namespace std;
int l,r,cnt=4,now=1;
map<int,int>a;
bool prime(int x){
	if(x<=1)return 0;
	for(int i=2;i*i<=x;i++)
		if(!(x%i))return 0;
	return 1;
}
signed main(){
	a[1]=2,a[2]=3,a[3]=5,a[4]=7;
	while(a[cnt]<100000){
		if(now>cnt)break;
		for(int i=1;i<=9;i+=2)
			if(prime(a[now]*10+i))
				a[++cnt]=a[now]*10+i;
		now++;
	}
	cin>>l>>r;
	for(int i=1;i<=cnt;i++)
		if(l<=a[i]&&a[i]<=r)
			cout<<a[i]<<"\n";
	return 0;
}

可以通过 $n=10^{18}$ 时的数据（但是上面代码里的循环边界要改为 $10^{18}$），时空复杂度均接近 $O(1)$，大圆满。玄学

最后...

完结撒草！——蓝棉锦

写作不易，求赞awa。