Problem 7

Problem

By listing the first six prime numbers: \(2, 3, 5, 7, 11\), and \(13\), we can see that the \(6\)th prime is \(13\).

What is the \(10\,001\)st prime number?

Julia

include("euler.jl")

function find_next_prime(primes)
    n = primes[end]
    while true        
        n += 2

        not_prime = false
    
        for q ∈ primes
            not_prime = Euler.divides(q, n)
            if not_prime
                break                
            end            
        end

        if not_prime 
            continue 
        end
    
        return(n)        
    end    
end;

function find_n_primes(n::Integer)
    primes = [2, 3]
    while length(primes) < n
        next_prime = find_next_prime(primes)
        push!(primes, next_prime)
    end

    return primes
end;

p7() = find_n_primes(10_001)[end];
p7()

104743

using BenchmarkTools;
@benchmark p7()

BenchmarkTools.Trial: 63 samples with 1 evaluation.
 Range (min … max):  79.486 ms … 79.618 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     79.518 ms              ┊ GC (median):    0.00%
 Time  (mean ± σ):   79.521 ms ± 22.772 μs  ┊ GC (mean ± σ):  0.00% ± 0.00%
                 ▂  ▂█ █            ▂                          
  █▅█▅▁▁▁██▅█▅▅█▅█▁▁█████▅▅▅██▁█▅▅███▅▁▁▁▁▅▁▁▁▁▁▁▅▁▁█▁▁▁▁▁▁▁▅ ▁
  79.5 ms         Histogram: frequency by time        79.6 ms <
 Memory estimate: 326.56 KiB, allocs estimate: 9.