一道C++编程题，叫可爱的质数最好用和谢谢各路大神了！

更新时间2019-08-09 19:54:23

1. 可爱的质数

【问题描述】

小凯最近对质数产生了兴趣。他发现，有些质数的各位数字之和还是质数，于是他把这种质数称作“可爱的质数”。比如，23 是质数，其各位数字之和即 2+3=5 还是质数，所以23 是“可爱的质数”。而 19 就不是“可爱的质数”，因为它的各位数字之和即 1+9=10 不是质数。现在小凯想考考你，他给你一个整数 n，问你不超过 n 的“可爱的质数”有多少个？

【输入】

输入文件名为 cute.in。

输入共 1 行，一个整数 n。

【输出】

输出共 1 行，一个整数，表示不超过 n 的“可爱的质数”的个数。

【输入输出样例 1】

【输入输出样例说明】

不超过 20 的“可爱的质数”有 2、3、5、7、11，共 5 个，所以输出 5。

【数据范围】

对于 50%的数据，0 < n ≤ 1,000 ；对于 80%的数据，0 < n ≤ 10,000 ；

对于 100%的数据， 0 < n ≤ 1,0000,000。

完整的程序参考（输入来自控制台，要来自文件，自己改下）

#include <iostream>
using namespace std;
//为提高效率，采用过滤法
//若没有过多内存限止，采用全局数组
bool isPrimes[10000001];
void Init(int n) //初始化，计算素数集合
{
for(int i=2; i<=n; ++i) //将每一位都初始化为是素数
{
isPrimes[i] = true;
}
isPrimes[2] = true; //2为素数
for(int j=2; j<=n; ++j)
{
if(isPrimes[j]==true) //如果j为素数，则它的倍数都不是素数
{
for(int m=2; j*m<=n; ++m) //它的倍数都不是素数
{
isPrimes[j*m] = false;
}
}
}
}
///判断各位和是否为素数
bool s_isPrimes(int n)
{
int s=0;
while(n)
{
s+=n%10;
n/=10;
}
return isPrimes[s];
}
int main()
{
int n,i,ct=0;
cin >> n;
Init(n);
for(i=2; i<=n; i++)
if (isPrimes[i] && s_isPrimes(i))
ct++;
cout << ct << endl;
return 0;
}

这个要看你自己了