Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- long long int mark[1000005]={0};
- long long int isprime[1000005];
- void sieve()
- {
- int i,j,k=0;
- mark[0]=1;
- mark[1]=1;
- for(i=2;i*i<=1000000;i++)
- {
- if(mark[i]==0)
- {
- for(j=i*i;j<=1000000;j+=i)
- {
- mark[j]=1;
- }
- }
- }
- }
- void prime()
- {
- sieve();
- int i,j,a,k,sum=0,count=0;
- for(i=2;i<=1000000;i++)
- {
- if(mark[i]==0)
- {
- a=i;
- sum=0;
- while(a!=0)
- {
- sum+=(a%10);
- a/10;
- }
- if(mark[sum]==0)
- count++;
- }
- isprime[i]=count;
- }
- }
- int main()
- {
- long long int a,t,b,c,i,j=0;
- sieve();
- prime();
- scanf("%lld",&t);
- for(i=1;i<=t;i++)
- {
- scanf("%lld %lld",&a,&b);
- c=isprime[b]-isprime[a-1];
- printf("%lld\n",c);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement