## NDIVPHI2 - N DIV PHI_N (Hard)

no tags

Given an integer N <= 1025000 find the smallest m <= N such that m/phi(m) is maximum. Where phi is euler's totient function.

### Input

The first line in the input gives the number of test cases T (T <= 200), and then T lines follow each containing an integer N.

### Output

Output the smallest required value of m.

### Example

`Input:110Output:6`

hide comments
 < Previous 1 2 Next > Sayak Haldar: 2015-01-27 19:51:11 precomputation+binary search got ac with c++ Last edit: 2015-01-28 20:03:54 [Lakshman]: 2014-04-12 07:40:17 Last edit: 2015-01-10 11:28:24 Deepanker Aggarwal: 2014-03-09 11:38:06 Please increase time limit for JAVA (Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2012-10-06 18:03:38 Finally AC, really hard problem :-) Pankaj Jindal: 2012-06-25 12:18:16 I am getting WA, can anyone paste some large test cases or if there is any corner case.. Thanks!!! Edit: Finally AC'ed Last edit: 2012-09-27 20:15:21 Vinay Saini: 2011-09-02 02:01:46 My c++ solution gives TLE while applying same concept, with haskell solution i got AC !! Michael T: 2011-07-04 17:43:46 Maybe haskell's gmp saves here. It definitely does. :) Last edit: 2011-07-12 11:21:33 hendrik: 2011-07-04 15:46:05 numerix: I use standard functions: ByteString.readInteger to convert and print for output. Nothing home made. Last edit: 2011-07-04 15:46:51 numerix: 2011-07-04 11:48:53 hendrik: But only with efficient I/O handling, I guess. hendrik: 2011-07-03 22:14:03 mukesh: never say never. For this one HASK can make it.

 Added by: SALVO Date: 2010-04-23 Time limit: 0.945s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: ADA95 ASM32 ASM64 BASH BF C CSHARP C++ 4.3.2 CPP CPP14 C99 CLPS LISP sbcl LISP clisp D ERL FORTRAN HASK ICON ICK JAVA JS-RHINO LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCALA SCM qobi SCM guile ST TCL TEXT WHITESPACE Resource: Frank Rafael Arteaga