这题需要判断 $n$ 以内的所有数是否为质数。

60 分：$O(\sqrt{n})$ 判断每个数是否为质数

如果一个个去判断，判断一个数是否为质数的时间复杂度为 $\sqrt{n}$，判断 $n$ 个就是 $n\sqrt{n}$，在 $n=5000000$ 时显然无法在一秒内完成。

#include <bits/stdc++.h>
using namespace std;
//返回 x 是否为质数 
bool isPrime(int x){
	if(x<2) return false;
	for(int i=2;i*i<=x;i++)
		if(x%i==0)
			return false;
	return true; 
}
int n;
int main()
{	
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		int sumI = 0;//i 的所有数位之和 
		for(int j = i; j > 0; j /= 10)
			sumI += j % 10; 
		if(isPrime(i)&&isPrime(sumI))
			cout<<i<<"\n";	
	}
	return 0;
}

100 分：埃氏筛法预处理 1~n 每个数是否为质数

我们可以使用时间复杂度为 $O(n\log{\log{n}})$ 的埃氏筛法完成本题。

#include <bits/stdc++.h>
using namespace std;
int n;
bool p[5000000+5]; //p[i]: i 是否为质数 
int main()
{	
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	//埃氏筛法，预处理 p[1]~p[n]
	for(int i=1;i<=n;i++)
		p[i]=true;
	p[1]=false;
	for(int i=2;i<=n;i++)
	{
		if(p[i]==false)	
			continue;
		//把质数的n以内的倍数都标记为合数 
		for(int j=i+i;j<=n;j+=i)
			p[j]=false;
	}
	//找二重质数	 
	for(int i=1;i<=n;i++){
		int sumI = 0;//i 的所有数位之和 
		for(int j = i; j > 0; j /= 10)
			sumI += j % 10; 
		if(p[i]&&p[sumI])
			cout<<i<<"\n";	
	}
	return 0;
}

也可以使用 $O(n)$ 时间复杂度的线性筛法（欧拉筛）完成。

int cntNum(int x)
{

}
int main()
{
    cin >> n;
    for (int i = 2; i <= n; ++i)
    {
        if (!vis[i])
        {
            pri[cnt++] = i;
            if (!vis[cntNum(i)])
                cout << i << "\n";
        }
        for (int j = 0; j < cnt; ++j)
        {
            if (1ll * i * pri[j] >= MAXN)
                break;
            vis[i * pri[j]] = 1;
            if (i % pri[j] == 0)
                break;
        }
    }

大致思路：埃氏筛法+数位分解

基本均在之前的课程讲过，故直接放代码。 由于担心直接通过递归数位分解在n很大的时候会超时，但是又不想写记忆化搜索，所以直接使用暴力方法。

标准的、更优秀的、更快速的、更完美的、更易于理解的代码请参见33DAI上传的题解

#include<bits/stdc++.h>
using namespace std;
bool pd[5000010];
int n;
int fenjie(int x)   //暴力数位分解 
{
	int BW=(x%10000000)/1000000;    //百万位 
	int SW=(x%1000000)/100000;  //十万位 
	int W=(x%100000)/10000;  //万位 
	int Q=(x%10000)/1000;  //千位 
	int B=(x%1000)/100;  //百位 
	int S=(x%100)/10;  //十位 
	int G=x%10;  //个位 
	return BW+SW+W+Q+B+S+G;
}
void start(int m)   //埃氏筛法 
{
	pd[1]=pd[0]=1;
	for(int i=2;i<=m;i++)
	{
		if(pd[i]==0)
		{
			for(int j=i+i;j<=m;j=j+i)
				pd[j]=1;
		}
	}
	return;
}
int main()
{
	cin>>n;
	start(n);
	for(int i=1;i<=n;i++)  //循环判断 
	{
		int sum=fenjie(i);
		if((pd[sum]==0)&&(pd[i]==0))
			cout<<i<<'\n';
	}
	return 0;
}