SPOJ.com - Problem NDIVPHI

NDIVPHI - N DIV PHI_N

#math #number-theory

Given an integers N ≤ 10⁴⁰ find the smallest m ≤ N such that m / phi(m) is maximum, where Phi is Euler's totient function.

There are twenty values for N.

N₁
N₂
.
.
.
N₂₀

Output twenty answers, one for each value of N in the input.

m₁
m₂
.
.
.
m₂₀

Input:
10
.
.

Output:
6
.
.

< Previous 1 2 Next >

	bashrc is back: 2011-06-30 16:03:13 haskell friendly problem :)
	Gurpreet Singh: 2011-01-22 10:25:44 Finally done!!!! Lots of silly mistakes.... I considered 91 as prime .... :( and there were others tooo Last edit: 2011-01-22 17:49:08
	sudipto das: 2010-10-09 22:31:25 Range is small enough........... I use linear search instead of binary search...........
	Frank Rafael Arteaga: 2010-04-24 12:47:29 Ravi, the data test is right. In your code: if n == 1: print '1' continue and T? you are reading more lines than 20 ;)
	Ravi Kiran: 2010-04-23 14:06:35 @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
	thomas anderson: 2010-04-22 20:47:56 is there more than one m where m/phi(m) is maximum and m<=N?
	Zhenlei Jia: 2010-04-22 13:40:48 Euler's totient function, see http://en.wikipedia.org/wiki/Euler%27s_totient_function
	Mohamed Ramzy: 2010-04-22 12:55:59 what is phi(m)??

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