Hello all
I am trying to solve this problem [ spoj.pl/problems/KPEQU1 ] 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^a25^a3 .....pk^ak . Could some one please tell me how to make this code more faster .
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