一個(gè)十進(jìn)制數(shù)饺窿，如果是素?cái)?shù)，而且它的各位數(shù)字和也是素?cái)?shù)移斩，則稱之為“美素?cái)?shù)”肚医，如29，本身是素?cái)?shù)向瓷，而且2+9 = 11也是素?cái)?shù)肠套，所以它是美素?cái)?shù)。
給定一個(gè)區(qū)間猖任，你能計(jì)算出這個(gè)區(qū)間內(nèi)有多少個(gè)美素?cái)?shù)嗎你稚？
每行輸入兩個(gè)整數(shù)L，R(1<= L <= R <= 1000000)，表示區(qū)間的左值和右值刁赖。
#define maxn 1000000+1
int num[maxn];
bool prime[maxn];
void getprime()
{
?????? memset(prime,true,sizeof(prime));//一開始假定所有數(shù)都是素?cái)?shù)
?????? prime[1]=false;//1肯定不是素?cái)?shù)
?????? int m=sqrt(maxn);
?????? for(int i=2;i<=m;i++){
??????????? if(prime(i)){
?????????????? for(int j=i+i;j<maxn;j=j+i)
??????????????? {? prime[j]=false;}
???????????? }
?????? }
}
int getsum(int n)
{
??? int sum=0;
??? while(n>0){
???????? sum+=n%10;
???????? n/=10;
??? }
??? return sum;
}
int main()
{
int cnt=0;
memset(num,0,sizeof(num));
??? for(int i=1;i<maxn;i++){
??????? if(prime[i]&&prime[getsum(i)]){
??????????? cnt++;
?????? }
?????? num[i]=cnt;
??? }
??? cout<<a[r]-a[l-1]<<endl;
}
