| Submit | All submissions | Best solutions | Back to list |
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 p-1 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 p-1. We put p=2 in class one. For example, p=89 is in class three, because p-1=2^3*11 and here 2 is in class one, but 11 is in class two (because 11-1=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.
| Added by: | Robert Gerbicz |
| Date: | 2012-09-18 |
| Time limit: | 1s-26.83s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | High School Programming League 2012/13 |
hide comments
|
2016-06-30 11:04:02 Bhuvnesh Jain
@Robert, could you please tell why I am getting TLE? Is my algorithm of pre-computation slow or more optimisations are required? The complexity for pre-computation is O(n + plogp), where n = 50000000 and p = number of primes below 50000000. Last edit: 2016-06-30 11:05:32 |
|
|
2014-06-15 19:21:55 Min_25
it seems that time limits are proportional to max {b}. |
|
|
2012-12-28 17:29:29 Ashish Lavania
@Robert, what are the number of cases in the last test case? Last edit: 2013-05-18 22:44:27 |
|
|
2012-12-09 14:05:23 Robert Gerbicz
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: 2012-12-09 14:07:05 |
RSS