Calculating Prime Factors in PHP

Here’s a PHP class to find the prime factorization of a number.

<?php
function primefactor($num) {
	$sqrt = sqrt($num);
	for ($i = 2; $i <= $sqrt; $i++) {
		if ($num % $i == 0) {
			return array_merge(primefactor($num/$i), array($i));
		}
	}
	return array($num);
}

$prime = primefactor(12590161); // this is a prime number
print_r($prime);

$composite = primefactor(65535); // this is a composite number
print_r($composite);

?>

As you can see above, there is a quick demonstration of how the function can be used. You may also want to take a look at a Project Euler Problem 3 for another way the function is used.

Do keep in mind that this is not the most efficient way to do the calculations, though it will work just fine for 99% of purposes. At some point in time I’ll have a post more focused on an efficient algorithm to calculate a number’s prime factors and whether it is prime or not.