埃氏筛法

本题可以用埃氏筛法解决，搭配有枚举和位数和（各个数位上数的和）

此代码中 prime函数是埃氏筛法；

add函数是求一个数各个数位上数的和；

mbf函数作用是逐一枚举 2~n 的每一个数，从a数组中调查 i 与 add(i) 是否都为质数。

#include <iostream>
using namespace std;
bool a[5000005];
int n;
void prime(int n)
{
    for (int i=2;i<=n;i++)
    {
        if(!a[i])
        {
            for (int j=i*2;j<=n;j+=i)
            {
                a[j]=1;
            }
        }        
    }
}
int add(int n)
{
    int sum=0;
    while(n>0)
    {
        sum+=n%10;
        n/=10;
    }
    return sum;
}
void mbf() 
{
    for (int i=2;i<=n;i++)
    {
        if (a[i]==0 && a[add(i)]==0)
        {
            cout << i << endl;
        }
    }
}
int main()
{
    cin >> n;
    prime(n);
    mbf();
    return 0;   
}

都看到这里了，就点个赞 ，投个币吧。

相信你在看完欧拉筛后可以很快编出欧拉筛的代码。

void Euler() // 欧拉筛
{
    for (int i = 2; i <= n; i++) // 因为我们知道,1肯定不是素数,所以从2开始筛就可以了
    {
        if (is_prime[i] == false) // 说明没有被标记过,是质数
            prime[++cnt] = i; // 将i存储在指数行列中
        for (int j = 1; j <= cnt; j++) // 从prime[i]开始一个个枚举
        {
            if (1ll * i * prime[j] > n) // 说明枚举的值超过了n
                break;
            is_prime[i * prime[j]] = true; // 对vis[i*prime[j]]进行标记
            if (i % prime[j] == 0) // 说明这个以及后面的数被标记过了
                break;
        }
    }
}

然后调用Euler后对每一个指数进行判断即可。

int main()
{
    scanf("%d", &n);
    Euler(); // 进行计算
    printf("2\n"); // 因为n一定>=2,所以一定会输出2
    for (int i = 3; i <= n; i += 2) // 因为偶数除了2都是合数
    {
        if (i / 10 == 0 && i != 9) // 说明这个数是1位数,并且不等于9
        {
            printf("%d\n", i);
            continue;
        }
        if (i == 9 || is_prime[i] == true) // 说明这个奇数不是质数
            continue;
        int i2 = i; // 如果更改i会陷入死循环,所以用i2进行计算
        now = 0; // 存储各位数之和
        while (i2 > 0) // 进行计算
        {
            now += i2 % 10;
            i2 /= 10;
        }
        if (is_prime[now] == false) // 说明这个数是二重质数
            printf("%d\n", i);
    }
    return 0;
}

测试通过，100分答案

运用埃氏筛法

#include <bits/stdc++.h>
using namespace std;
long long n,num,sum;
bool p[5000001];
int main()
{
	cin >> n;
	memset(p,1,sizeof(p));
	for (int i = 2;i <= n;i++)
	{
		if (p[i])
		{
			sum = 0;
			num = i;
			for (int j = i*2;j <= n;j += i)
			{
				p[j] = 0;
			}
			do
			{
				sum += num % 10;
			} while (num /= 10);
			if (p[sum])
			{
				cout << i << endl;
			}
		}
	}
	return 0;
}

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

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

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

cin >> n;
    //埃氏筛法
    memset(isP, true, sizeof(isP));
    tot = 0;
    isP[0] = isP[1] = false;
    for (int i = 2; i <= n; i++)
    {
        if (isP[i])
        {
            p[++tot] = i;
            //-----检测是否二重
            int cnt = 0;
            for (int j = i; j > 0; j /= 10)
                cnt += j % 10;
            if (isP[cnt])
                cout << i << "\n";
            //-----检测结束
            for (int j = i + i; j <= n; j += i)
                isP[j] = false;
        }
    }

也可以使用 $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;
        }
    }

埃氏筛+立刻判断，总时间复杂度O(n(log(log(n))))(<O(n))

#include <bits/stdc++.h>
using namespace std;
int is[5000005],n,k,p;
int main()
{
    cin >> n;
    for (int i = 2;i <= n;i++)
    {
        if (!is[i])
        {
            for (int j = 2 * i;j <= n;j += i)
            {
                is[j] = 1;
            }
            k = i;
            p = 0;
            while (k > 0)
            {
                p += k % 10;
                k /= 10;
            }
            if (!is[p])//现在判断，因为位置原理可知,数abcd……z(共k位) - abcd……z数字和 = 9999……9(k - 1个) * a + 999……9(k - 2个) * b…… ,结果>= 0，可以确保筛法正确
            {
                cout << i << endl;
            }
        }
    }
}

如果你认真看完了wiki中的欧拉筛法，就能很快解决第一步（筛出1~n以内的质数）

然后把筛出的数求数位和，再判断数位和是否为素数，是就输出该素数。

欧拉筛法、检查素数的时间复杂度都为 O(n), 参考代码如下

void func_prime_Euler()
{
    for (int i = 2; i <= n; i++) //从2开始筛查素数
    {
        if (is_prime[i] == false) //检查标记，未被标记则是素数，并把i加入数组
            prime[++cnt] = i;
        for (int j = 1; j <= cnt; j++) //枚举
        {
            if (i * 1ll * prime[j] > n) //检测当前值是否超过了n
                break;
            is_prime[i * prime[j]] = true; //标记
            if (i % prime[j] == 0) //检查这个以及后面的数被标记过了没
                break;
        }
    }
}
bool func_is_prime(int x) //这个解法比较慢，大家肯定有更好的解法！
{
	int f = 0;
	for (int i = 2; i <= x; i++) //枚举，统计因数
		if (x % i == 0) f++;
	if (f == 1) return true; //因为是从2开始枚举到n，所以f为1时就是素数
	return false; //否则返回不是
}

}

6

写题解请注意

鼓励大家写题解，但注意题解格式。

题解一定要有思路解析或代码注释，能否让别人理解你的思路

也是你的能力的检验，不要只放无意义的代码给大家复制，那就失去了做题的初心。

给代码两端加上这个会舒服一些

```cpp

你的代码

```

</span>

这个点在键盘的左上角tab上面那个键，注意切换输入法

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;//这是一个注释
    return 0;
}

请注意严禁抄袭题解，写题解不要只放代码，需加上你的思路或代码注释。

抄袭题解一经发现直接取消成绩。

题解被删除的可能

1. 代码不符合格式规范
2. 没有思路讲解或者没有注释，
3. 无意义的题解

大家携手共同维护一个良好的编程环境，如果一经发现，多次作乱。可能会被管理员拉黑，请注意，一旦拉黑即失去登陆资格。