|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
#include <iostream> #include <cstdio> #include <sstream> #include <string> using namespace std; bool prime[1000001]; bool firstPrime[1000001]; int primeCount[1000001]; bool checkdigit(int a) { int sum; if(a<10) return 1; else { sum=0; while(a) { sum+=a%10; a/=10; } if(firstPrime[sum]==0) return 1; else return 0; } return 0; } int main() { int cnt=0; prime[0]=1; prime[1]=1; firstPrime[0]=1; firstPrime[1]=1; primeCount[0]=cnt; primeCount[1]=cnt; for(int i=2;i<1000001;i++) { if(prime[i]==0) { if(!checkdigit(i)) prime[i]=1; else { cnt+=1; } for(int j=i+i;j<1000001;j+=i) { prime[j]=1; firstPrime[j]=1; } } primeCount[i]=cnt; } int t,a,b,add; scanf("%d",&t); while(t--) { add=0; scanf("%d%d",&a,&b); if(firstPrime[a]==0 && checkdigit(a)) add=1; printf("%d\n",primeCount[b]-primeCount[a]+add); } return 0; } |