Hello all
I am trying to solve this problem [ https://www.spoj.pl/problems/KPEQU
] but getting time limit exceed . My algorithm is given equation can
be written as ( N! - x) * ( N! - y) = (N!) ^2. Now the number of
solution of any number N will be (2a1+1) *(2a2+1) ....(2ak + 1) where
N! = 2^a1 * 3^a2*5^a3 .....pk^ak . Could some one please tell me how
to make this code more faster or how to improve the algorithm . I am
posting my code but some times due to indentation issue , this code
may throw compiler error. You can have a look here in case of
compilation error [ http://hpaste.org/47479/spoj_kpequ ].
Thank you
import Data.List
isprime :: Integer -> Bool
isprime n | n<=1 = False
| otherwise = all ( (/=0).mod n ) . takeWhile ( \x -> x*x<= n) $
[2..]
--count prime p in list from p to n
count :: Integer -> Integer -> Integer
count n p = sum . map snd . map ( until ( \( x , _ ) -> mod x p /=
0 ) ( \( x , y ) -> ( div x p , y+1 ) ) ) . zip [p..n] $ [0,0..]
plist ::[Integer]
plist = filter isprime [2..]
solve :: Integer -> String
solve 1 = show 1
solve n = show a where
p = takeWhile ( <=n) plist
a = foldl (\acc x -> acc * ( 2 * ( count n x ) + 1 ) ) 1 p
main = interact $ unlines . map ( solve . read ) . init . lines
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
