Ferramentas de Utilizador

Ferramentas de Site


dev_geral:haskell:snippet:euler_347

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

O maior inteiro <=100 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 <=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 <=100 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
dev_geral/haskell/snippet/euler_347.txt · Esta página foi modificada pela última vez em: 2018/05/14 21:37 (Edição externa)