spoj ABA12D problem solution

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

HII guys.....this problem seem easy brute force will not pass here even optimised brute force ......... there is nice logic behind this problem.............. I did this problem using hard code...............then i found out the tricky ness of problem............ you can find out the logic of the problem after applying brute force........... m-1 using tricky solution m-2 using hard optimised code this below solution is using method-1 if u want to check my hard code u can read in my another post......... logic::m-1 1..when you find out number between 1 and 10^6 the answer is only 37. i.e only 37 number for which there sum of divisor is prime.... 2..u can intilise these 37 number to an array........... 3..for each test case just check that how many elements of array lies between a and b. I HOPE YOU GOT THE LOGIC MY AC SOLUTION IS.... #include<bits/stdc++.h> using namespace std; #define LL long long LL arr[37]={2, 4, 9, 16, 25, 64, 289, 729, 1681, 2401, 3481, 4096, 5041, 7921, 10201, 15625, 17161, 27889, 28561, 29929, 65536, 83521, 85849, 146689, 262144, 279841, 458329, 491401, 531441, 552049, 579121, 597529, 683929, 703921, 707281, 734449, 829921}; int main() { LL t,a,b,count,i; scanf("%lld",&t); while(t--) { count=0; scanf("%lld %lld",&a,&b); for(i=0;i<37;i++) { if(arr[i]>=a && arr[i]<=b) count++; } printf("%lld\n",count); } return 0; }