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 (minmax):  15.578 μs39.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 (minmax):  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.