Skip to content

Instantly share code, notes, and snippets.

@massimo-zaniboni
Created January 13, 2016 12:49
Show Gist options
  • Save massimo-zaniboni/0499802e8019a4173c28 to your computer and use it in GitHub Desktop.
Save massimo-zaniboni/0499802e8019a4173c28 to your computer and use it in GitHub Desktop.
Problem: Find the largest prime factor of 600851475143.
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment