FINDPRM - Finding Primes
One commonly used method to calculate all primes in the range [2 .. n] is to start with the number 2, mark it as prime, and mark all its multiples (excluding itself) as not prime. Then, we find the next smallest unmarked number, mark it as prime, and mark all its multiples (excluding itself) as not prime. Continuing this way, we get a list of all primes.
Now, let us say that we modified the above algorithm, and start with n instead of 2. We mark it as prime, and mark all its factors (excluding itself) as not prime. Then we find the next greatest unmarked number, mark it as prime, and mark all its factors (excluding itself) as not prime. Continuing this way, we get a list of all primes.
Now you wonder, given a value of n, how many numbers are such that both the above algorithms will mark them as prime?
Input
The first line contains T the number of test cases. Each of the next T lines contain an integer n.
Output
Output T lines, one for each test case, containing the required answer.
Example
Input: 3 2 4 7 Output: 1 1 2
Constraints
1 ≤ T ≤ 100000
2 ≤ n ≤ 10000000
hide comments
hassanarif63:
2017-07-03 09:44:52
Precomputation makes it a cakewalk!! |
|
Shubham Jadhav:
2017-05-12 11:19:05
I am using regular sieve, with binary search, but still getting TLE Also using scanf and printf. Any idea why? |
|
gautam:
2016-10-11 08:47:51
nice one...!! |
|
vinay12345:
2016-08-23 20:01:07
learnt a lot after 3 hours..3 solution...but 1 accepted...finally
|
|
vaibhav138:
2016-07-21 20:53:37
Similar question ALICESIE |
|
goelnandan:
2016-07-07 17:15:58
i am using a similar approach as in "prime genenrator" whats wrong?
|
|
vaibhav goyal:
2016-07-05 19:33:45
why fastScan with cin and cout is not working??
|
|
Dilpreet:
2016-07-04 15:59:50
Good One..!
|
|
Piyush Kumar:
2016-06-25 00:29:04
Is there something wrong with the input files? Fast IO is giving TLE!
|
|
nightwolf_9197:
2016-06-24 14:12:02
precompute simple sieve :)
|
Added by: | Varun Jalan |
Date: | 2010-01-24 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: PERL6 |
Resource: | own problem used for Codechef Snackdown Onsite |