# My Weblog

## SPOJ 6556. N DIV PHI_N

SPOJ 6556. N DIV PHI_N is same as Project Euler problem 69.$\frac n {\phi (n) } = \frac { p_0p_1...p_r} { (p_0-1)(p_1-1)...(p_r-1) }$ and this quantity will be maximum when $p_0*p_1....p_r$ is maximum and $(p_0-1)*(p_1-1)...(p_r-1)$ is minimum.$1 -\frac 1 p$ will be minimal for small p hence $\frac p {p-1}$ will maximal so take product of the primes and product of primes should not exceed N. Accepted Haskell code.You can also have look here.

import Data.List
import qualified Data.ByteString.Char8 as BS

isprime :: [Integer]
isprime = 2:3:filter prime [2*k+1 |  k<-[2..]]

prime :: Integer -> Bool
prime n = all ((/=0). mod n  ).takeWhile ( <= ( truncate.sqrt.fromIntegral $n) )$ isprime

helpSolve :: [Integer] -> Integer -> Integer -> Integer
helpSolve (x:xs) n ret
| ret*x > n = ret
| otherwise = helpSolve xs n ( x * ret )

solve :: Integer -> BS.ByteString
solve n = BS.pack.show $a where a = helpSolve isprime n 1 readInt :: BS.ByteString -> Integer readInt x = case BS.readInteger x of Just ( i , _ ) -> i Nothing -> error " upseperable ints " main = BS.interact$ BS.unlines.map ( solve .readInt ) . BS.lines