thoga31

Largest integer divisible by two primes (Euler, 347)

Aug 27th, 2013
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. -- ### Project Euler, problem 347 ### --
  2. import Data.List (nub)
  3.  
  4. firstPrimes n = takeWhile (<=n) primes
  5.  
  6. primes = 2 : filter isPrime [3,5..]
  7.   where
  8.     isPrime n = all (/=0) . map (n `mod`) $ [2..squareRoot n]
  9.     squareRoot = truncate . sqrt . fromIntegral
  10.  
  11. factors n = f n (reverse $ firstPrimes n)
  12.   where
  13.     f _ [] = []
  14.     f 1 _ = []
  15.     f m l@(x:xs) | m `mod` x == 0 = x : f (m `div` x) l
  16.                  | otherwise      = f m xs
  17.  
  18. fn_m a b lim = myHead . map fst . filter (λ(x, xs) -> (b `elem` xs) && (a `elem` xs)) . filter ((== 2) . length . snd) . zip [lim, lim-1..2] $ map (nub . factors) [lim, lim-1..2]
  19.   where
  20.     myHead [] = 0
  21.     myHead xs = head xs
  22.  
  23. fn_s n = sum $ map (λ(x,y) -> fn_m x y n) l
  24.   where
  25.     l = myZip (firstPrimes $ n-1) (tail $ firstPrimes n)
  26.  
  27. myZip _ [] = []
  28. myZip [] _ = []
  29. myZip a@(x:xs) b@(y:ys) = map (λn -> (x, n)) b ++ myZip xs ys
  30.  
  31. main = do
  32.   putStrLn . show $ fn_m 2 3 100   -- control of "fn_m" (function M(p,q,N))
  33.   putStrLn . show $ fn_s 100       -- control of "fn_s" (function S(N))
  34.   putStrLn . show $ fn_s 10000000  -- problem
Advertisement
Add Comment
Please, Sign In to add comment