1

I am trying to find the largest prime factor of 600851475143 and here is the code:

function find($x){
    $lpf = 2;

    while($x > $lpf){
        if($x%$lpf == 0){
            $x = $x/$lpf;
            $lpf = 2;
        }else{
            $lpf +=1;
        }
    }

    echo $lpf;
}

find(600851475143);

It would echo just 2 but the algorithm is working fine with smaller numbers. What is the problem?

  • 4
    are you on a 32bit php? 600851475143 is WAY outside the representable range of a standard php signed 32bit int. – Marc B Mar 07 '14 at 17:33
  • @MarcB PHP_INT_SIZE is 4, so apparently yes( can you please check whether it will work if you are on 64bit? –  Mar 07 '14 at 17:49
  • you're on a 32bit (4 byte) install. I'm on a 64bit install with intsize=8. running the code here returns 6857. – Marc B Mar 07 '14 at 18:48
  • You are overly cautious and thus slowing the algorithm down. You can safely remove the $lpf = 2; statement. Also explore the concept of a number wheel. Last big thread on the problem: http://stackoverflow.com/q/22153481/3088138, also look at the general search result http://stackoverflow.com/search?q=600851475143 – Lutz Lehmann Mar 08 '14 at 11:21

0 Answers0