Problem 5

Problem

$2520$ is the smallest number that can be divided by each of the numbers from $1$ to $10$ without any remainder.

What is the smallest positive number that is evenly divisibledivisible with no remainder by all of the numbers from $1$ to $20$?

Julia (using lcm)

p5() = lcm(1:20...);
p5()

232792560

using BenchmarkTools;
@benchmark p5()

BenchmarkTools.Trial: 10000 samples with 1000 evaluations.
 Range (min … max):  1.132 ns … 3.647 ns  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     1.142 ns             ┊ GC (median):    0.00%
 Time  (mean ± σ):   1.140 ns ± 0.038 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%
  ▁                                                  █       
  █▁▁▁▁▃▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█▁▁▁▁▄ ▂
  1.13 ns        Histogram: frequency by time       1.14 ns <
 Memory estimate: 0 bytes, allocs estimate: 0.

Julia

include("euler.jl")

function prime_decomposition(n::Integer)
    possible_primes = Euler.sieve_of_eratosthenes(n)
    temp_n = n
    dec = Int32[]

    while temp_n > 1
        for p ∈ possible_primes
            q, r = divrem(temp_n, p)            
            if iszero(r)
                temp_n = temp_n ÷ p
                push!(dec, p)
                break
            end
        end
    end
    return dec
end;

function p5()
    decomposition = map(prime_decomposition, 2:20)
    distinct_primes = vcat(decomposition...) |> unique

    count_matrix = 
    map(distinct_primes) do p
        map(decomposition) do d
            count(==(p), d)
        end
    end |> stack

    primes_powers = map(maximum, eachcol(count_matrix))

    n = (distinct_primes .^ primes_powers) |> prod

    return n
end;

p5()

232792560

using BenchmarkTools;
@benchmark p5()

BenchmarkTools.Trial: 10000 samples with 6 evaluations.
 Range (min … max):  5.078 μs … 701.066 μs  ┊ GC (min … max):  0.00% … 97.51%
 Time  (median):     5.646 μs               ┊ GC (median):     0.00%
 Time  (mean ± σ):   6.691 μs ±  22.319 μs  ┊ GC (mean ± σ):  13.51% ±  4.02%
         ▃▆▇█▇▃▂                                               
  ▁▁▁▂▃▅█████████▇▆▄▄▃▃▂▂▂▂▂▂▂▂▂▂▂▂▂▁▂▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁ ▂
  5.08 μs         Histogram: frequency by time        7.99 μs <
 Memory estimate: 12.66 KiB, allocs estimate: 142.