## SPOJ 6556. N DIV PHI_N

SPOJ 6556. N DIV PHI_N is same as Project Euler problem 69. and this quantity will be maximum when is maximum and is minimum. will be minimal for small p hence 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

Advertisements

[…] 6560. N DIV PHI_N (Hard) also accepted using the same idea accept using a bit memoization. Precalculation of product of prime table 10^25000 and linear […]

Pingback by SPOJ 6560. N DIV PHI_N (Hard) « My Weblog | July 17, 2011 |