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. Return the last number which gets scratched when the Sieve of Eratosthenes is run with the given maxNum.
The first line contains T,denoting the number of testcases.
For each testcase, there is a line contains maxNum.
T<=100
maxNum will be between 4 and 2000000000, inclusive.
For each testcase, print a line contain the answer.
4 18 5 100 400
15 4 91 361
Migrated from old NTUJ.
TCO 10 round 3
| No. | Testdata Range | Score |
|---|