题目

只能被 1 和本身整除的数称为质数。
请问在 1 （含）到 1000000（含）中，有多少个质数的各个数位上的数字之和为 23 。
提示：599 就是这样一个质数，各个数位上的数字之和为 5+9+9=23 。

朴素筛质数算法

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N =1e6+10;
bool st[N];
int primes[N];
int cnt,sum;
int get_primes(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(st[i]) continue;
        primes[cnt++]=i;
        for(int j=i;j<=n;j+=i) st[j]=true;
    }
    return primes[N];
}
int main()
{
    int n =1e6;
    get_primes(n);

     int sum=0;
    for(int i=0;i<cnt;i++)
    {
        int ans=0;
        int j=primes[i];
        while(j>0)
        {
            ans+=j%10;
            j/=10;
        }
        if(ans==23) sum++;
    }
    cout<<sum<<endl;
    return 0;
}