幸运数问题

如果一个数各个数位上的数字之和是质数，并且各个数位上的数字的平方和也是质数，则称它为幸运数。给定x，y，求x，y之间（包含x，y，即闭区间[x,y]）有多少个幸运数。例如1到20之间有4个幸运数，它们是11,12,14,16，像因为1+1 = 2是质数，1^2 + 1^2 = 2也是质数等等。给定函数原型，其中1<=x<=y<=1000000000，请完成函数，实现上述功能。

庞果网做的太水了，提交规则不明，而且不能马上看到结果，易做图。

打表代码如下：

[cpp]
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<bitset>
using namespace std;

const int FF = 1000000000;
const int inf = 81*9+5;
bitset<inf> prime;

void init()
{
    prime.set();
    prime[0] = prime[1] = 0;
    for(int i=4;i<inf;i+=2)
        prime[i] = 0;
    double t= sqrt(inf*1.0);
    for(int i=3;i<=t;i+=2)
    {
        if(prime[i])
        {
            int k = i*i, p =i+i;
            for(int j=k;j<inf;j+=p)
                prime[j] = 0;
        }
    }
}

int judge(int n)
{
    int s = 0, t = 0;
    while(n)
    {
        s += n%10;
        t += (n%10)*(n%10);
        n /= 10;
    }
    return prime[s] && prime[t];
}

int main()
{
    init();
    freopen("a.txt","w",stdout);

    int cnt = 0,num = 0;
    for(int i=1;i<=FF;++i)
    {
        cnt += judge(i);
        if(i%100000 == 0)
        {
            printf("%d,",cnt);
            ++num;
            if(num%100 == 0)
                puts("");
            cnt = 0;
        }
    }

    return 0;
}

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<bitset>
using namespace std;

const int FF = 1000000000;
const int inf = 81*9+5;
bitset<inf> prime;

void init()
{
prime.set();
prime[0] = prime[1] = 0;
for(int i=4;i<inf;i+=2)
  prime[i] = 0;
double t= sqrt(inf*1.0);
for(int i=3;i<=t;i+=2)
{
  if(prime[i])
  {
   int k = i*i, p =i+i;
   for(int j=k;j<inf;j+=p)
    prime[j] = 0;
  }
}
}

int judge(int n)
{
int s = 0, t = 0;
while(n)
{
  s += n%10;
  t += (n%10)*(n%10);
  n /= 10;
}
return prime[s] && prime[t];
}

int main()
{
init();
freopen("a.txt","w",stdout);

int cnt = 0,num = 0;
for(int i=1;i<=FF;++i)
{
  cnt += judge(i);
  if(i%100000 == 0)
  {
   printf("%d,",cnt);
   ++num;
   if(num%100 == 0)
    puts("");
   cnt = 0;
  }
}

return 0;
}

正式代码：

[cpp]
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<bitset>
using namespace std;

const int inf = 81*9+5;
bitset<inf> prime;

void init()
{
    prime.set();
    prime[0] = prime[1] = 0;
    for(int i=4;i<inf;i+=2)
        prime[i] = 0;
    double t= sqrt(inf*1.0);
    for(int i=3;i<=t;i+=2)
    {
        if(prime[i])
        {
            int k = i*i, p =i+i;
            for(int j=k;j<inf;j+=p)
                prime[j] = 0;
        }
    }
}

int judge(int n)
{
    int s = 0, t = 0;
    while(n)
    {
        s += n%10;
        t += (n%10)*(n%10);
        n /= 10;
    }
    return prime[s] && prime[t];
}

/**************************************************************************/

int sum[] =
{
9716,10446,10121,9077,9886,9140,7887,8856,8496,7646,10447,10348,9410,9631,10060,9214,9575,8990,8400,8370,10122,9410,10262,9740,9251,9591,9175,9086,8840,8965,9077,9631,9740,8792,9495,9067,8375,9051,8885,7935,9887,10060,9250,9495,9642,8936,8740,9570,8586,9076,9140,9214,9591,9067,8936,9176,8981,8638,8983,8781,7888,9575,9175,8375,8741,8981,8417,8400,8740,7430,8856,8990,9086,9050,9570,8637,8400,9182,8460,8530,8496,8400,8841,8885,8586,8983,8740,8460,8411,8390,7646,8370,8965,7936,9076,8781,7430,8530,8390,7451,
10447,10348,9410,9631,10060,9214,9575,8990,8400,8371,10348,9117,9227,9965,8792,9512,9599,8232,8901,8988,9410,9226,9905,9037,9011,8895,8936,9120,8461,8557,9631,9965,9038,9126,8984,8550,8681,8897,8637,8612,10060,8792,9011,8984,8897,8836,9286,8153,9097,9182,9213,9512,8895,8550,8835,8746,9197,9120,8995,8836,9575,9599,8936,8681,9286,9198,9150,9212,8930,8917,8990,8232,9121,8897,8153,9120,9212

补充：软件开发 , C++ ,