NDIVPHI - N DIV PHI_N

Given an integer N <= 1040 find the smallest m <= N such that m/phi(m) is maximum.

Input

N1
N2
.
.
.
N20

Output

m1
m2
.
.
.
m20

Example

Input:
10
.
.
Output:
6
.
.

Added by:Frank Rafael Arteaga
Date:2010-04-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:ProjectEuler

hide comments
2011-06-30 16:03:13 bashrc is back
haskell friendly problem
:)
2011-01-22 10:25:44 Gurpreet Singh
Finally done!!!!
Lots of silly mistakes....
I considered 91 as prime .... :( and there were others tooo

Last edit: 2011-01-22 17:49:08
2010-10-09 22:31:25 sudipto das
Range is small enough...........
I use linear search instead of binary search...........
2010-04-24 12:47:29 Frank Rafael Arteaga
Ravi, the data test is right. In your code:

if n == 1:
print '1'
continue

and T? you are reading more lines than 20 ;)
2010-04-23 14:06:35 Ravi Kiran
@Frank
Thank u frank.Im actually a newbie in python,hence my skills are bad!
I got ac changing that part!:)

Last edit: 2010-05-01 10:54:57
2010-04-22 20:47:56 thomas anderson
is there more than one m where m/phi(m) is maximum and m<=N?
2010-04-22 13:40:48 Zhenlei Jia
Euler's totient function, see http://en.wikipedia.org/wiki/Euler%27s_totient_function
2010-04-22 12:55:59 Mohamed Ramzy
what is phi(m)??
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.