The largest prime factor with php

Question

So, I wrote php program to find the largest prime factor with php and I think it is quite optimal, because it loads quite fast. But there is a problem, it doesn't count very big numbers's prime factors. Here is a program:

function is_even($s) {

    $sk_sum = 0;

    for($i = 1; $i <= $s; $i++) {

        if($s % $i == 0) { $sk_sum++; }     

    }

    if($sk_sum == 2) {

        return true;

    }

}

$x = 600851475143; $i = 2; //x is number

while($i <= $x) {

        if($x % $i == 0) {

            if(is_even($i)) {

                $sk = $i; $x = $x / $i;

            }

        }

    $i++;

}

echo $sk;

Answer 1

Well, every language has it's own (while usually same) limitations, so if you exceed this php's limit, you can't get any higher. Max Integer is 9E18.

Answer 2

You should read about Prime testing and Sieving.

In particular, you don't need to test whether each of your divisors is prime.

Something like the following would be faster.

while($i <= $x) 
{
    while ($x % $i == 0)
    {
        $sk = $i;
        $x = $x / $i;
    }
    $i++;
}

You can also stop your outer loop when $i reaches sqrt($x), and if you haven't found a divisor yet then you know $x is prime.

Answer 3

The largest non-overflowing integer in PHP is stored in the constant PHP_INT_MAX.

You won't be able to work with integers larger than this value in PHP.

To see all of PHP's predefined constants, just use:

<?php
echo '<pre>';
print_r(get_defined_constants());
echo '</pre>';
?>

PHP_INT_MAX probably has a value of 2,147,483,647.

To handle numbers of arbitrary precision in PHP, see either the GMP or BC Math PHP extensions.