Project Euler: Problem 3

Problem: What is the highest prime factor of n? In this case: n = 600851475143

Q: What is the simplest way to find the highest prime factor of n?
A: Try dividing n by every number from 2 (the smallest prime) to n – 1. If the remainder of the division is zero, check the number for primeness and keep a record of the highest value.

Q: How do we reduce the search space?
A: Several ways based on what we know about prime numbers.
A1: Skip even numbers, since an even number (other than 2) cannot be prime and therefore cannot be a prime factor. This reduces the search space by 50%.
A2: Only check potential factors from n – 1 to floor(sqrt(n)). After that we will have checked all of the factors because any factor f < sqrt(n) will have a corresponding factor f’ > sqrt(n).

Reducing the search space by skipping even numbers and numbers greater than the square root of n reduces the number of potential factors to check in this case from 600851475141 (n – 2) to 387573 (sqrt(n) / 2).

Q: How do we tell if a factor is prime?
A: Divide it by all of the prime numbers below the factor. Any number which is composite (i.e. not prime) will have at least one prime factor of its own. Conversely, if a number has no prime factors, it is prime.

Q: How do we generate a list of all prime numbers below a given factor?
A: Use the Sieve of Eratosthenes. As with reducing the search space, we only need to generate a list of all prime numbers to floor(sqrt(factor)). Note that this method will not scale to extremely large numbers, as building the sieve would require too much memory.

<?php

declare(strict_types=1);
error_reporting(E_ALL);

define('SIEVE_UNKNOWN', -1);
define('SIEVE_NOT_PRIME', 0);
define('SIEVE_PRIME', 1);
define('FIRST_PRIME', 2);

define('FACTORISE_TARGET', 600851475143);

function prime_numbers(int $max_prime_candidate) : array
{
    $sieve = array_fill(0, $max_prime_candidate + 1, SIEVE_UNKNOWN);
    $primes = [];

    $sieve[FIRST_PRIME] = SIEVE_PRIME;
    $current_prime = FIRST_PRIME;
    $primes_found = 1;

    for ($i = FIRST_PRIME; $current_prime != 0 && $i <= $max_prime_candidate; $i++)
    {
        $next_prime = 0; // assume this prime will be the last
        $step = $current_prime;

        // Mark all multiples of current prime as non-prime
        for ($j = $current_prime + $step; $j <= $max_prime_candidate; $j += $step)
        {
            $sieve[$j] = SIEVE_NOT_PRIME;
        }

        // Find the next unknown element after the current prime,
        // this is the next prime
        for ($k = $current_prime + 1; $next_prime === 0 && $k <= $max_prime_candidate; $k++)
        {
            if ($sieve[$k] === SIEVE_UNKNOWN)
            {
                $sieve[$k] = SIEVE_PRIME;
                $next_prime = $k;
                $primes_found++;
            }
        }

        // Set current prime to be the next prime.
        // If there is no next prime ($next_prime === 0), this will end the search.
        $current_prime = $next_prime;
    }

    for ($s = FIRST_PRIME; $s <= $max_prime_candidate; $s++)
    {
        if ($sieve[$s] === SIEVE_PRIME)
        {
            $primes[] = $s;
        }
    }

    return $primes;
}

// Highest possible factor at the start is the square root of the target
$highest_possible_factor = intval(floor(sqrt(FACTORISE_TARGET)));

// Build list of factors from 2 to the highest possible factor
$factors = [];

for ($candidate_factor = 2; $candidate_factor < $highest_possible_factor; $candidate_factor++)
{
    if (FACTORISE_TARGET % $candidate_factor === 0)
    {
        $other_factor = FACTORISE_TARGET / $candidate_factor;
        $factors[] = $candidate_factor;
        $factors[] = $other_factor;

        // Because we check factors from the lowest value, the other factor is
        // potentially the new highest possible factor
        if ($highest_possible_factor > $other_factor)
        {
            $highest_possible_factor = $other_factor;
        }
    }
}

// If we have found no factors, the target is prime and therefore has
// no highest prime factor
if (count($factors) === 0)
{
    die("No prime factors found\n");
}

// Sort factors
sort($factors, SORT_NUMERIC);

// Which of the factors are prime? First build an array of primes up to the
// square root of the highest factor.
// The alternative is to build an array of primes up to the highest factor, as
// that would allow us to do a lookup instead of multiple divisions, however
// that would also increase the memory requirements for the array by an order
// of highest_factor (which could be >1m).
$highest_factor = $factors[count($factors) - 1];
$max_prime_candidate = intval(floor(sqrt($highest_factor)));
$primes = prime_numbers($max_prime_candidate);

$highest_prime_factor = 0;

$factors_count = count($factors);
$primes_count = count($primes);

// Check each factor for primeness by dividing it by our primes. All composite
// numbers have at least one prime factor.
for ($i = 0; $i < $factors_count; $i++)
{
    // Assume a target is prime until we successfully factorise it
    $target_factor = $factors[$i];
    $is_prime = true;

    for ($j = 0; $is_prime && $j < $primes_count && $primes[$j] < $target_factor; $j++)
    {
        if ($target_factor % $primes[$j] === 0)
        {
            $is_prime = false;
        }
    }

    if ($is_prime)
    {
        $highest_prime_factor = $target_factor;
    }
}

print("$highest_prime_factor\n");