PAGAIN - Prime Again

no tags 

In this problem, you have to find the nearest prime number smaller than N. (3 <= N <= 2^32)

Input

The first line contains an integer T specifying the number of test cases. (T <= 10000)

T lines follow, each line contains an integer N.

Output

For each test case, output the result on one line.

Example

Input:
3
5 
10
17

Output:
3
7
13

hide comments
akt_1998: 2017-04-24 18:12:51

Sieve :)
Ac after 8 tle

anurag44: 2017-04-17 23:07:37

Today I learnt following things about C++ :
1. unsigned is faster than long long (using long long gives TLE whereas unsigned passed)
2. Choosing version of compiler can change your answer from AC to WA. (i submitted using C++ 4.3.2 ,it got AC whereas the same code using latest complier C++14 gives wrong answer. God knows why ? .

shubham2305: 2017-04-17 21:45:34

unsigned int AC long long int TLE
* NO need of miller rapin just good implementation of seive

Last edit: 2017-04-17 21:46:22
Sarthak Munshi: 2016-06-08 15:20:02

10 TLEs and ongoing using Miller-Rabin . No idea how to proceed from hereon .

Last edit: 2016-06-12 18:35:51
GAURAV CHANDEL: 2016-02-24 12:10:51

Rabin miller will do it ..

Archit Gupta: 2016-02-20 16:40:54

Lot of TLE even after sieve,miller rabin and fermat please help

Mukul Chandel: 2015-10-25 16:25:02

people using miller rabbin and getting TLE make sure you use UNSIGNED long long datatype. cost me 2 TLE's.

Last edit: 2015-10-27 04:16:13
kuhan26: 2015-09-29 16:23:21

Fermat's theorem giving TLE :/

Ayur Jain: 2015-06-21 10:55:49

Miller-Rabin/Segmented Prime Sieve .. Everything is giving TLE! :/ I think requires too much of constant and data types optimisation.

_R0b_: 2015-04-27 21:48:12

sieve :)


Added by:Race with time
Date:2008-12-25
Time limit:0.620s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET