Project Euler Problem 3 – Largest prime factor

Project Euler Problem 3 is the first problem in which I realized that the brute-force computation is not the best way to achieving the results. Here is the problem description:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

The idea is to compute the biggest prime factor of the number 600851475143. Fortunately I did not understand idea very well and I start looking for the biggest prime number under the 600851475143 number. Here is the code for searching the biggest prime number smaller than 10000.

<?php 
$endNumber = 10000; 
$primeArray = array(2);

for ($i=2;$i<=$endNumber;$i++) {
        $isPrime = null; 
        $isNotPrime = null; 
        foreach ($primeArray as $prime) {
                switch ($i%$prime == 0) {
                        case true:
                                $isNotPrime = true; 
                                break;
                        case false:
                                $isPrime = true;
                                break;
                }
                if ($isPrime == true && $isNotPrime == false) {
                        if ($prime === end($primeArray)) {
                                array_push($primeArray, $i);
                        }
                }
        }
}

foreach ($primeArray as $num) {
	echo $num."<br>";
};
?>

When I made this code I realized something is wrong. Server default response exceeded default 30s and server outputed error. Brute force is not definitely not the right way to search for the bug prime numbers.

Computing the big prime number (and anything around  the 600 billions number is a big number) takes enormous computational power. Does the Problem 3 really ask me to compute such difficult computations?

I check an online resources for the algorithms for computing  the big prime numbers. I found out that I did not understand the Problem 3 description correctly. Instead of looking for the biggest prime number under 600851475143 the idea is to actually find the biggest prime factor of the number 600851475143 . This is the task from the Math lecture of an elementary school .

<?php
define('NUMBER', 600851475143);
$whileEnd = NUMBER;
$number = NUMBER;
$division = 2;
$primeFactor = array();

while ($division <= $whileEnd) {
	if (fmod($number, $division) == 0) {
		$number = $number/$division;
		array_push($primeFactor, $division);
		// echo $number." - ".$division.". <br>";
	} else {
		$division++;
	}
	$whileEnd = round(NUMBER/$division) + 1;
}

echo "The biggest prime is ".end($primeFactor)." and last round ended at ".$division." .";
?>

The idea is simple. Every number is possible to divide on a multiple of several prime numbers, for example the number 90 can be divide on the multiple of 2*3*3*5 where the number 5 is the biggest prime factor. So let’s try to divide the original number starting from the number 2.

If the number 2  is the prime number, we divide a reminder further by the number 2. We repeat the divide till the reminder is not dividable by current number.

If the number is not dividable by the current number, we increase the division number by 1 and try the whole process  with the remainder again.

We do it until (current number division the original number) times . Anything bigger this can not be the prime number of the original number. Thus by increasing the division we decrease the threshold for the end of loop.

Improvements for the Problem 3

I believe this is the algorithm for which exist many improved versions doing the faster computation of the prime numbers. While reviewing the code the best way to speed up the loop would be cleverly get rid of the all multiple of the all previous prime numbers. Unfortunately we can not use a Fibonacci algorithm from the previous Project Euler Problem 3.

Hint

While working on the algorithm I encountered big problem with modulo. Using a normal operator % with such big number leads to incorrect results caused by float. The PHP math function fmod provide correct result.

<?php
$number = 600851475143;
$division = 3;
echo $number%$division;        // result 0
echo fmod($number, $division); // result 2
?>