HS12PRIM  Classification from Erdős and Selfridge
Erdős Pál and John Selfridge classified prime numbers in this way: for a prime p, if the largest prime factor of p1 is 2 or 3, then p is in class one. Otherwise, p is in class c+1 where c is the largest of the classes of the prime factors of p1. We put p=2 in class one. For example, p=89 is in class three, because p1=2^3*11 and here 2 is in class one, but 11 is in class two (because 111=2*5 and here 2 and 5 are in class one). Your task is to count the number of primes in each class up to class thirteen for a given (closed) interval.
Input
The first line contains the number of test cases T, where T≤1000. Each of the following T lines contains two integers a,b where 0≤a≤b≤50000000. There are 4 input sets for 10 points.
Output
Output the case number, followed by the distribution of the primes in each class up to class 13 in the (closed) interval [a,b]. See the sample input/output for the correct format!
Example
Input: 3 2 100 23 23 0 50000000 Output: Case 1: There are 10 primes in class 1. There are 9 primes in class 2. There are 5 primes in class 3. There are 1 primes in class 4. There are 0 primes in class 5. There are 0 primes in class 6. There are 0 primes in class 7. There are 0 primes in class 8. There are 0 primes in class 9. There are 0 primes in class 10. There are 0 primes in class 11. There are 0 primes in class 12. There are 0 primes in class 13. Case 2: There are 0 primes in class 1. There are 0 primes in class 2. There are 1 primes in class 3. There are 0 primes in class 4. There are 0 primes in class 5. There are 0 primes in class 6. There are 0 primes in class 7. There are 0 primes in class 8. There are 0 primes in class 9. There are 0 primes in class 10. There are 0 primes in class 11. There are 0 primes in class 12. There are 0 primes in class 13. Case 3: There are 54 primes in class 1. There are 14196 primes in class 2. There are 364182 primes in class 3. There are 1029984 primes in class 4. There are 939493 primes in class 5. There are 458831 primes in class 6. There are 150902 primes in class 7. There are 34878 primes in class 8. There are 7085 primes in class 9. There are 1310 primes in class 10. There are 203 primes in class 11. There are 15 primes in class 12. There are 1 primes in class 13.
Warning: A naive algorithm will probably solve only the first input set.
hide comments
Bhuvnesh Jain:
20160630 11:04:02
@Robert, could you please tell why I am getting TLE? Is my algorithm of precomputation slow or more optimisations are required? The complexity for precomputation is O(n + plogp), where n = 50000000 and p = number of primes below 50000000. Last edit: 20160630 11:05:32 

Min_25:
20140615 19:21:55
it seems that time limits are proportional to max {b}. 

Ashish Lavania:
20121228 17:29:29
@Robert, what are the number of cases in the last test case? Last edit: 20130518 22:44:27 

Robert Gerbicz:
20121209 14:05:23
To get AC you have to solve all input sets (these are very different difficulties)! My sample but somewhat optimized solution runs in 10 seconds. Last edit: 20121209 14:07:05 
Added by:  Robert Gerbicz 
Date:  20120918 
Time limit:  1s26.83s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  High School Programming League 2012/13 