19 1 s 128 MB
The Sieve of Erathosthenes is an ancient method used to find all prime numbers between 2 and a given upper bound maxNum, inclusive. It works like this:
make a list of all numbers between 2 and maxNum, inclusive
for x = 2 to maxNum if x is not scratched for y = 2 to maxNum/x if x*y is not scratched, scratch x*y end for end if end for
In this fashion, every composite number in the range will get scratched while every prime number will remain unscratched. Print the last number which gets scratched when the Sieve of Eratosthenes is run with the given maxNum.
The first line of the input gives the number of test cases, $T$ $(1 \leq T \leq 200)$.
For each test case one positive integer maxNum will be given in a line. MaxNum will be between $4$ and $2\times10^9$, inclusive.
For each test case, print the last number as explained in the problem statement, in one line.
Sample Input | Sample Output |
---|---|
4 18 5 100 400 | 15 4 91 361 |