Caleb Oki Caleb Oki - 2 months ago 15
PHP Question

Finding a factor of 600851475143 that lies between 2 and 100

I wrote a script to find a factors of 600851475143 that lies between 2 and 100. However I get different values when I ran the script on my local machine and when I ran it on Phpfiddle.org On Phpfiddle I get the correct answer of 71 but on my machine the script simple returns 100 which is wrong. What could be causing this? The code is below

<?php

$n = 600851475143;

for ($i=2; $i < 100; $i++) {

$result = ($n/$i);

if (is_int($result)) {

break;
return $i;
}
}
echo $i;
?>

Answer

PHP Manual: Arithmetic Operators:

The division operator ("/") returns a float value unless the two operands are integers (or strings that get converted to integers) and the numbers are evenly divisible, in which case an integer value will be returned.


Your local machine is using 32-bit integers, the largest of which is 2147483647. Either you've got a 32-bit build or you're on Windows using a PHP version prior to 7.

Because 600851475143 is larger than your maximum integer it is converted to a float, and your division will therefore always return a float as well.

If you

var_dump(600851475143/71)

on your local system you'll get

float(8462696833)

while any system using 64-bit integers will give you

int(8462696833)

as 600851475143 and 71 are well within 64-bit bounds.


A method that works across both 32 and 64-bit systems is to check if there is remainder of division using fmod(), e.g.:

$n = 600851475143;

for ($i=2; $i < 100; $i++) {
    if (!fmod($n, $i)) {
        break;
    }
}

echo $i;

Will give you 71 regardless of integer size.

Comments