Ferramentas de Utilizador

Ferramentas de Site


dev_geral:haskell:snippet:euler_216

Primalidade dos números 2n^2-1 (Euler, 216)

Considere os números t(n) da forma t(n)=2n^2-1 onde n>1. Os primeiros números do género são 7, 17, 31, 49, 71, 97, 127 e 161. Constata-se que apenas 49=7*7 e 161=7*23 não são primos. Para n<=10000 existem 2202 números t(n) que são primos.

Quantos números t(n) são primos para n<=50~000~000?

in Project Euler, problem 216

isPrime n = all (/= 0) . map (n `mod`) $ [2..squareRoot n]
  where
    squareRoot = truncate . sqrt . fromIntegral
 
list = map (subtract 1 . (*2) . (^2)) [2..]  -- 2n^2-1
 
main = do
  putStrLn . show $ solveit 10000     -- caso de controlo
  putStrLn . show $ solveit 50000000  -- caso em estudo
    where
      solveit n = length . filter isPrime $ take (n-1) list

Colocando a fórmula numa função à parte:

-- isPrime...
 
list = map t [2..]
t = subtract 1 . (*2) . (^2)  -- t(n) = 2n^2-1
 
main = do
  -- output...
    where
      solveit n = length . filter isPrime $ takeWhile (<= (t n)) list
dev_geral/haskell/snippet/euler_216.txt · Esta página foi modificada pela última vez em: 2018/05/14 21:37 (Edição externa)