Finding the prime factors

This lesson covers prime factorisation in Julia, with the aim of understanding a number-theory algorithm built on loops.

Prime factorisation expresses a number as a product of primes. Try dividing from 2 upwards, and whenever a number divides, keep dividing by it.

The sample code starts at d = 2 and, while n divides by d, records the factor with push!(factors, d) and keeps dividing with n = div(n, d), increasing d by one when it no longer divides — repeating until n reaches 1.

A common early stumble is the nested loop structure. The outer loop increases the divisor d while the inner one keeps dividing for as long as it can — that two-stage arrangement is the key to understanding it.

It is an important idea spanning mathematics and computer science, and underpins the security of cryptography such as RSA.

📖 Reference code

function prime_factors(n)
    factors = Int[]
    d = 2
    while n > 1
        while n % d == 0
            push!(factors, d)
            n = div(n, d)
        end
        d += 1
    end
    factors
end

println(prime_factors(60))
println(prime_factors(97))

✍️ Your code

Type your code, then press "Run"

🧪 This site can't compile or run Julia directly, so it checks on the spot whether what you typed matches the reference code (scoring happens entirely in your browser — nothing is sent anywhere).