My Weblog

Blog about programming and math

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 
Advertisements

June 17, 2011 - Posted by | Programming | , , ,

1 Comment »

  1. […] 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 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: