Problem: Find the largest prime factor of 600851475143.

LPF.hs

module Main where

import System.Environment

--
-- Problem: Find the largest prime factor of 600851475143.
--

question = 600851475143

-- ------------------------------------------------------------
-- Possible solution on:
-- https://wiki.haskell.org/Euler_problems/1_to_10#Problem_3
-- 
-- with personal notes.

-- NOTE: this is the true definition of primes:
-- a prime is in the list if it is 2, 3, 5, 7, 9, etc.. (2 and all odd numbers),
-- and at the same time it has no factors, except itself.
primes = 2 : filter (null . tail . primeFactors) [3,5..]

primeFactors :: Integer -> [Integer]
primeFactors n = factor n primes
  where
    factor n (p:ps) 
        | p*p > n        = [n]
        | n `mod` p == 0 = p : factor (n `div` p) (p:ps)
        | otherwise      =     factor n ps

problem n = last $ primeFactors n

solution = problem question

-- -------------------------------------------------------------
-- Variant 2
--

-- | This variant is apparently simpler and faster:
--   a loop on all possible primes, applying a fast and simple division.
primeFactors_v2 :: Integer -> [Integer]
primeFactors_v2 n = factor n maybePrimes
  where

    maybePrimes = 2 : [3, 5 ..]

    factor 1 _ = []

    factor n (p:ps) 
        | p*p > n        = [n]
          -- NOTE: there are no chances that there is another number dividing n so it is prime.

        | n `mod` p == 0 = p : factor (n `div` p) (p:ps)
          -- NOTE: with n == 18, we first divide by p == 3,
         --  so when we test with p == 9, p == 18, and so on,
         --  the division is not executed, because it is already catched from the
         --  first true prime number.

        | otherwise      =     factor n ps

problem_v2 n = last $ primeFactors_v2 n

solution_v2 = problem_v2 question

-- ---------------------------------------
-- Benchmarks
--
-- time ./Primes 1
-- 64937323262
-- 
-- real	0m3.015s
-- user	0m3.012s
-- sys	0m0.004s
--
-- /Primes 2
-- 64937323262
-- 
-- real	0m6.972s
-- user	0m6.973s
-- sys	0m0.000s
--
-- so the second version also if it seems simpler, in reality execute more tests
-- performing more divisions, and it is slower!
--

bench_f f n
  = sum $ map f [2 .. n] 

bench n = bench_f problem n

bench_v2 n = bench_f problem_v2 n 

test_v2 n = all (\x -> problem_v2 x == problem x) [2 .. n]

main = do
  let c = 1000000
  a <- getArgs
  case a of
    [] -> print $ "1 for version 1 of alg, 2 for version 2"
    ["t"] -> print $ test_v2 2000
    ["1"] -> print $ bench c
    ["2"] -> print $ bench_v2 c
    ["s1"] -> print $ solution
    ["s2"] -> print $ solution_v2