Question

How to find the largest prime factor of a number in PHP

Answer 1

function largestPrimeFactor($n) {
    $div = 2;
    $maxPFact = -1;

    while ($n != 0) {
        if ($n % $div != 0) {
            $div++;
        } else {
            $maxPFact = $n;
            $n /= $div;
            if ($n == 1) {
                break;
            }
        }
    }

    return $maxPFact;
}

echo largestPrimeFactor(124) . "\n"; // 2 x 2 x 31
echo largestPrimeFactor(288) . "\n"; // 2 x 2 x 2 x 2 x 2 x 3 x 3
echo largestPrimeFactor(1288) . "\n"; // 2 x 2 x 2 x 7 x 23
echo largestPrimeFactor(100000000) . "\n"; // 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5



/*
run:

31
3
23
5

*/

 

70+ SQL courses for beginners and professionals

Answer 2

// Returns the largest prime factor of n
function largestPrimeFactor($n) {
    $largest = -1;

    // Step 1: Remove all factors of 2
    while ($n % 2 == 0) {
        $largest = 2;
        $n /= 2;
    }

    // Step 2: Try odd factors from 3 to sqrt(n)
    for ($i = 3; $i * $i <= $n; $i += 2) {
        while ($n % $i == 0) {
            $largest = $i;
            $n /= $i;
        }
    }

    // Step 3: If n is still > 2, it is a prime number
    if ($n > 2) {
        $largest = $n;
    }

    return $largest;
}

$n1 = 124; // 2 x 2 x 31
$n2 = 288; // 2 x 2 x 2 x 2 x 2 x 3 x 3
$n3 = 1288; // 2 x 2 x 2 x 7 x 23
$n4 = 100000000; // 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5
$n5 = 600851475143; // 71, 893, 1471, 6857

echo "Largest prime factor: " . largestPrimeFactor($n1) . PHP_EOL;
echo "Largest prime factor: " . largestPrimeFactor($n2) . PHP_EOL;
echo "Largest prime factor: " . largestPrimeFactor($n3) . PHP_EOL;
echo "Largest prime factor: " . largestPrimeFactor($n4) . PHP_EOL;
echo "Largest prime factor: " . largestPrimeFactor($n5) . PHP_EOL;


/*
run:

Largest prime factor: 31
Largest prime factor: 3
Largest prime factor: 23
Largest prime factor: 5
Largest prime factor: 6857

*/

 

70+ SQL courses for beginners and professionals