EPR - PrePrimes
A number is preprime if it has exactly 4 positive integer divisors. For example, 6 is preprime because its divisors are 1, 2, 3, and 6. The integers 6, 8, 10, 14 form the beginning of an infinite sequence of preprime numbers. Find the n-th element of this sequence, where n is a 1-based index.
Input
First line contains an integer T <= 20 - the number of test cases. Following each line contains a single integer 1<= N <= 1000000.
Output
For each test case, print Nth preprime in a single line.
Example
Input:
4
2
4
24
43765
Output:
8
14
77
193539
hide comments
nadstratosfer:
2018-05-25 11:58:16
Classical-grade problem, if at the easier end of the NT category. Good constraints, several approaches possible, fun to optimize. Damn shame it's been rotting in tutorial for 7 years with less than a dozen solvers.. Admins, if possible please add #number-theory tag. |
|
John and the cows:
2013-08-17 15:47:37
yes, finally AC :) |
Added by: | Mahesh Chandra Sharma |
Date: | 2011-01-28 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |