O maior inteiro divisível por dois primos (Euler, 347)

Nota: O maior inteiro \(\leq100\) que é divisível apenas por ambos os primeors 2 e 3 é 96, já que \(96=2^5*3\). Para dois primos distintos \(p\) e \(q\), seja \(M(p,q,N)\) o maior inteiro positivo \(\leq N\) divisível apenas por ambos \(p\) e \(q\), e \(M(p,q,N)=0\) se tal número não existir.

Por exemplo:

• \(M(2,3,100)=96\)
• \(M(3,5,100)=75\) e não \(90\) uma vez que 90 é divisível não só por 2 e 3 mas também por 5.
• \(M(2,73,100)=0\) uma vez que não existe nenhum número inteiro positivo \(\leq100\) que seja divisível por ambos 2 e 73.

Seja \(S(N)\) a soma de todos os \(M(p,q,N)\) distintos. \(S(100)=2262\).

Encontre \(S(10~000~000)\).

in Project Euler, problem 347

import Data.List (nub)

firstPrimes n = takeWhile (<=n) primes

primes = 2 : filter isPrime [3,5..]
  where
    isPrime n = all (/=0) . map (n `mod`) $ [2..squareRoot n]
    squareRoot = truncate . sqrt . fromIntegral

factors n = f n (reverse $ firstPrimes n)
  where
    f _ [] = []
    f 1 _ = []
    f m l@(x:xs) | m `mod` x == 0 = x : f (m `div` x) l
                 | otherwise      = f m xs

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]
  where
    myHead [] = 0
    myHead xs = head xs

fn_s n = sum $ map (λ(x,y) -> fn_m x y n) l
  where
    l = myZip (firstPrimes $ n-1) (tail $ firstPrimes n)

myZip _ [] = []
myZip [] _ = []
myZip a@(x:xs) b@(y:ys) = map (λn -> (x, n)) b ++ myZip xs ys

main = do
  putStrLn . show $ fn_m 2 3 100   -- controlo de "fn_m" (função M(p,q,N))
  putStrLn . show $ fn_s 100       -- controlo de "fn_s" (função S(N))
  putStrLn . show $ fn_s 10000000  -- resolução do exercício