문제1614--SieveOfEratosthenes

1614: SieveOfEratosthenes

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 103  통과: 19
[제출] [채점기록] [묻고답하기]

문제 설명

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.

입력 예시 Copy

4
18
5
100
400

출력 예시 Copy

15
4
91
361

출처/분류