Skip to content

Instantly share code, notes, and snippets.

@icio
Created December 5, 2010 18:13
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save icio/729309 to your computer and use it in GitHub Desktop.
Save icio/729309 to your computer and use it in GitHub Desktop.
largest_prime_factor
<?php
test();
/**
* The largest prime factor
*
* The provided number is not considered a factor of itself.
*
* @param int $n The number we wish to find a factor of
* @return int|false false is returned when there are no prime factors
*/
function largest_prime_factor($n)
{
$limit = floor(sqrt($n));
$lpx = false; // Largest prime x
for ($x = 2; $x <= $limit; $x++)
{
$y = $n / $x;
if (is_int($y) && is_prime($y)) {
return $y;
}
if (is_prime($x)) {
$lpx = $x;
}
}
return $lpx;
}
/**
* All factors of a number
*
* Note that when there are an odd number of factors returned, $n is a square
* number and the last factor is the square root.
*
* @param int $n
* @return array
*/
function factors($n)
{
$limit = sqrt($n);
$factors = array();
for ($x = 2; $x <= $limit; $x++)
{
$y = $n / $x;
if (is_int($y)) {
$factors[] = $x;
if ($x != $y) $factors[] = $y;
}
}
return $factors;
}
/**
* Whether a number is prime or not
*
* @param int $n The number in question
* @param bool
*/
function is_prime($n)
{
if ($n < 4) return true;
$limit = sqrt($n);
// Check if the square root is a factor
// -- if it is, $n is not prime
if (is_int($limit))
return false;
// Check the lower components of pairs of factors
// -- if any exist, $n is not prime
for ($x = 2; $x <= $limit; $x++)
if (($n % $x) == 0)
return false;
// Otherwise, $n is prime
return true;
}
function test()
{
header("Content-Type: text/plain");
echo "Key: !sqrt >lpf\n\n";
for ($n = 1; $n < 40; $n++)
{
$factors = factors($n);
sort($factors);
$sqrt = sqrt($n);
$lpf = largest_prime_factor($n);
$factors = array_map(function($f) use($sqrt, $lpf) {
if ($f == $sqrt) {
if ($f == $lpf) {
return '!>'.$f;
}
return '!'.$f;
} else if ($f == $lpf) {
return '>'.$f;
}
return $f;
}, $factors);
echo $n, ': [', implode(', ', $factors) ,"]\n";
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment