Prime Factorization

In this lesson you will learn the prime factorization algorithm - expressing a number as a product of primes - and see mathematics and programming meet. This is for anyone searching for "PHP prime factorization".

Prime factorization means expressing a number as a product of primes. Try dividing by 2, then 3, and so on; whenever a divisor works, keep dividing by it.

The sample code raises $d from 2 upwards, dividing $n for as long as it divides evenly. When it no longer does, $d increases by one and the next number is tried, repeating until $n reaches 1 and every prime factor has been collected.

A common stumbling block for beginners is the different roles of the inner and outer loops. The inner loop asks "how many times does this number divide?" while the outer while loop moves on to the next candidate. Grasp that two-stage structure and the whole algorithm falls into place.

It is an idea spanning mathematics and computer science that underpins the security of cryptography such as RSA. Since 1 divides everything, it is excluded from prime factorization.

📖 Reference code

<?php
function primeFactors($n) {
    $factors = [];
    $d = 2;
    while ($n > 1) {
        while ($n % $d === 0) {
            $factors[] = $d;
            $n = intdiv($n, $d);
        }
        $d++;
    }
    return $factors;
}

print_r(primeFactors(60));
print_r(primeFactors(97));

✍️ Your code

Type your code, then press "Run"

🧪 This site can't compile or run PHP 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).