如何降低这个算法的复杂度
这是庞果上的一个题：如果一个数各个数位上的数字之和是质数，并且各个数位上的数字的平方和也是质数，则称它为幸运数。 给定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，请完成函数，实现上述功能。 时间不超过3s.
我实现了一个最简单的，时间太长了，求高人给出优化的思路。
下面是我的代码
算法 性能优化 C/C++
#include <iostream>
#include <math.h>
typedef unsigned long int uli;
using namespace std;
bool IsPrime(uli a)//是否素数
{
bool flag=true;
if(a==1)
flag=false;
if(a==2)
flag=true;
if(a==3)
flag=true;
if(a>=4)
{
for(int i=2;i<=sqrt(a);i++)
{
if(a%i==0)
{ flag=false;
return flag;
break;
}
}
}
return flag;
}
bool IsLucky(uli a)//是否幸运数
{
int sumPlus=0;
uli sumMulti=0;
int b;
while(a>=10)
{ b=a%10;
sumPlus+=b;
sumMulti+=(b*b);
a=a/10;
}
b=a;
sumPlus+=b;
sumMulti+=(b*b);
return (IsPrime(sumPlus)&&IsPrime(sumMulti));
}
uli Lucky(uli start,uli end)//start和end之间，幸运数的个数
{ uli count=0;
for(int i=start;i<=end;i++)
{
if(IsLucky(i)==1)
count+=1;
}
return count;
}
int main()
{
cout<<Lucky(1,1000000000);
return 0;
}
