Problem 3

Problem

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

What is the largest prime factor of the number \(600851475143\)?

Julia

include("euler.jl")

function p3(n = 600851475143)
  Euler.prime_factors(n) |> maximum
end;

p3()

WARNING: replacing module Euler.

6857

using BenchmarkTools;
@benchmark p3()

BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  15.578 μs … 39.393 μs  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     15.669 μs              ┊ GC (median):    0.00%
 Time  (mean ± σ):   16.353 μs ±  1.768 μs  ┊ GC (mean ± σ):  0.00% ± 0.00%
  █▆▂                             ▁▂▂▁▁              ▁        ▁
  ███▇█▅▄▅▅▇▃▅▃▅▄▄▅▄▄▅▅▅▇▅▃▄▄▅▁▁▅▇███████▇▅▆▆▇▇████████▇▇▆▇▇▇ █
  15.6 μs      Histogram: log(frequency) by time      22.1 μs <
 Memory estimate: 144 bytes, allocs estimate: 2.

Julia (calculating all the primes beforehand)

include("euler.jl")

function p3()
  n = 600851475143
  
  # get all primes lesses than sqrt(n)
  possible_primes = Euler.sieve_of_eratosthenes(isqrt(n)) # see prelude
  
  # get the biggest one
  id = findlast(x -> n % x == 0, possible_primes)    
  return possible_primes[id]
end;

p3()

WARNING: replacing module Euler.

6857

using BenchmarkTools;
@benchmark p3()

BenchmarkTools.Trial: 1966 samples with 1 evaluation.
 Range (min … max):  2.255 ms …   4.357 ms  ┊ GC (min … max): 0.00% … 20.66%
 Time  (median):     2.458 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   2.542 ms ± 224.887 μs  ┊ GC (mean ± σ):  2.84% ±  5.96%
         ▅▇█▄▄▂▁                                               
  ▁▁▁▁▂▃▇███████▆▅▄▄▃▂▂▂▂▂▂▁▁▁▂▁▂▁▁▁▁▂▁▁▂▂▂▃▂▂▂▂▂▂▁▂▁▁▁▁▁▁▁▁▁ ▂
  2.26 ms         Histogram: frequency by time        3.31 ms <
 Memory estimate: 6.48 MiB, allocs estimate: 8.