Haskell
ProjectEuler

Project EulerをHaskellで解いていく(Problem3: Largest prime factor)


TL;DR

Haskellの勉強を兼ねてProject Eulerを解いていきます。

始めたばかりでわからないことが多いのでコメント頂けると嬉しいです。


問題文


The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

13195 の素因数は 5, 7, 13, 29 である.

600851475143 の素因数のうち最大のものを求めよ.



コード

primes::Int -> [Int]

primes 1 = []
primes n = x : primes (n `div` x)
where
factors n = [x | x <- [1..n], n `mod` x == 0]
x = (factors n) !! 1

gcdPrime::Int -> Int
gcdPrime n = maximum $ primes n

main::IO()
main = do
print $ gcdPrime 600851475143

うーん…なんかもうちょっと良い実装がありそう…