Ir para o conteúdo

Inteiros geradores de primos (Euler, 357)

Nota: Considere os divisores de 30: 1,2,3,5,6,10,15,30. Pode-se constatar que, para todo o divisor \(d\) de 30, \(d+30/d\) é primo.

Encontre a soma de todos os números inteiros positivos \(n\) que não excedam \(100~000~000\), tais que, para qualquer divisor \(d\) de \(n\), \(d+n/d\) é primo.

in Project Euler, problem 357

isPrime :: Int -> Bool
isPrime n = all (/=0) . map (n `mod`) $ [2..squareRoot n]
  where
    squareRoot = truncate . sqrt . fromIntegral

divisors :: Int -> [Int]
divisors n = filter ((== 0) . (n `mod`)) [1..n `div` 2]

solveit :: [Int]
solveit = map fst . filter (λ(n, d) -> all isPrime $ map (λx -> x + n `div` x) d) $ zip [1..] (divisors [1..])

main = do
  putStrLn . show . sum $ takeWhile (<=100000000) solveit