<?php /**
 * Author: David Mottern
 * This was inspired by Project Euler problem 3.
 * https://projecteuler.net/problem=3
 * It's not meant to be a final polished project.
 *
 * Largest Prime Factor
 * Problem 3
 * The prime factors of 13195 are 5, 7, 13 and 29.
 * What is the largest prime factor of the number 600851475143 ?
 *
 * I've written a more general solution where you can pass any positive integer
 * and the largest prime factor for that integer will be returned. If the passed
 * number is itself prime than that number will be returned since it is its own
 * largest prime factor.
 *
 * In order to work with large integers, this uses the PHP GMP extension.
 * http://php.net/manual/en/ref.gmp.php
 *
 * This is live on the web at http://mottern.com/projecteuler/Problem3/
 * To solve for the problem described, for example, you would call it as follows:
 *         http://mottern.com/projecteuler/Problem3/?product=600851475143
 * This will also work if the values are sent in a Post rather than a Get.
 */

/**
 * Find the largest prime factor of $product
 *
 * @param int $product
 *      Find the largest prime factor of this number.
 *      It must be a positive integer (or a string of
 *      digits representing one).
 *
 * @return string
 *      The largest prime factor. If $product is itself
 *      a prime then $product will be returned.
 */
function largest_prime_factor($product) {
    // Convert $product into a gmp object.
    $gmpproduct = gmp_init($product);

    // gmp_prob_prime uses Miller-Rabin's probabilistic test for primarily. With reps=20
    // the odds of a false negative or positive are extremely small.
    if (gmp_prob_prime($gmpproduct, 20) > 0) {
        // The value is itself prime so just return it and exit.
        return gmp_strval($gmpproduct);
        exit ;
    } else {
        // Create a gmp object with a value of zero.
        $gmpzero = gmp_init(0, 10);
        // A variable is needed to save the largest found so far.
        $gmplargest = $gmpproduct;

        // Search from 2 to the square root
        $gmpproductsqrt = gmp_sqrt($gmpproduct);
        for ($i = gmp_init(2, 10); gmp_cmp($i, $gmpproductsqrt) <= 0; $i = gmp_nextprime($i)) {
            if (gmp_cmp(gmp_mod($gmpproduct, $i), $gmpzero) == 0) {
                // We've found the divisor. It's less than or equal to the square root so the
                // other factor will be larger or equal and may be the one we're interested in.
                // So we will test it for primality.
                if (gmp_prob_prime(gmp_div($gmpproduct, $i), 20) > 0) {
                    // It's prime! We have our answer.
                    return gmp_strval(gmp_div($gmpproduct, $i));
                    exit ;
                } elseif (gmp_prob_prime($i, 20) > 0) {
                    // The smaller divisor may be prime. If so save it in case it's the largest.
                    $gmplargest = $i;
                }
            }
        }
        // If we fall out of the for loop, then the answer
        // has been store in $gmplargest.
        return gmp_strval($gmplargest);
    }
}

// Show usage message for both errors and warnings.
set_error_handler("warning_handler", E_WARNING);
function warning_handler() {
    throw new Exception();
}

// Main Code
try {
    if (isset($_REQUEST['show_source'])) {
        show_source(__FILE__);
        exit ;
    }

    if (!isset($_REQUEST['product']) || !is_numeric($_REQUEST['product'])) {
        throw new Exception();
    }
    echo 'The Largest Prime Factor of ' . $_REQUEST['product'] . ' = ' . largest_prime_factor($_REQUEST['product']);
} catch (Exception $e) {
    //        Show the usage message regardless of the exception type.
    echo $e . '<br>';
    echo 'usage: <i>index.php?product=x</i> with product being an integer value > 0.';
    echo '<br>View PHP source: <A href="http://mottern.com/projecteuler/Problem3/?show_source">http://mottern.com/projecteuler/Problem3/?show_source</A>';
}
?>