Largest Prime Factor of Number in PHP or QBasic [closed]

Question

I was solving the 3rd problem at Project Euler which requires me to calculate the largest prime factor of 600851475143 which I think is a really large number (more than 6 billion).

QB64

At first, I tried solving this problem using QB64.

CLS
n = 600851475143
FOR x = 1 TO n
    IF n MOD x = 0 THEN
        FOR y = 1 TO (x / 2) - 1
            IF x MOD y = 0 THEN
                factor = y
            END IF
        NEXT y
        IF factor = 1 THEN
            ans = x
        END IF
    END IF
NEXT x
PRINT ans

However, on running the program, QB64 would appear busy executing the program, but no result would appear even after waiting for a long time.

QuickBasic 4.5

On getting no help from a compiler, I switched to QuickBasic 4.5 which is an interpreter. I executed the same code, but on trying to run the program, QuickBasic would trigger the following error on the line where I define the number.

Overflow

And, the program wouldn't execute at all.

Repl.it / QBasic

Getting no success, I tried using an online interpreter. View the live code at repl.it

On executing the same code on repl.it, the results were similar to what I got for QB64

PHP

I termed this as a limitation for the QBasic language and hence re-wrote the same logic in PHP.

$n = 600851475143;
for($x = 1; $x <= $n; $x++){
    if($n % $x == 0){
        for($y = 1; $y < $x/2; $y++){
            if($x % $y == 0){
                $factor = $y;
            }
        }
        if($factor == 1){
            $ans = $x;
        }
    } 
}
echo $ans;

Localhost

On executing this code in my local server (http://localhost:8000) I got no result, instead, the following error:

Maximum execution time of 30 seconds exceeded -- at line 5

I increased the max_execution_time from the php.ini to a few hours. However, I got now result from the code as it never executed completely. I waited for more than 6 hours, but the code continued to execute indefinitely without giving any result.

Online PHP compilers

I then tried a number of online compilers like:

• repl.it

Live code here.

• WritePHPOnline
• PHPFiddle

However, none of them could give me the result as they would either never stop executing or would show the maximum execution time error.

So, my question is, How can I SUCCESSFULLY execute this code to solve my problem? Do I need to:

• Use a different, more efficient Compiler / Interpreter
• Switch to a different language altogether
• Make my logic even more concise to reduce execution time

Note: When I used the above codes with a smaller number like 13195, the result was exactly correct, i.e., 29.

Answer 1

Finding prime factor is a common problem. Because they are hard to find, prime numbers are used in cryptography. You can read more here.

Now, in your question, you are looking for the largest prime factor of a huge number $n. Your approach is to test all numbers from 1 to $n. While this is accurate, is is not optimal, as you can see it takes more than 6 hours.

First loop : $n=600851475143 iterations

The first thing I would change is the loop logic : since you are looking for the largest prime factor, begin with $n instead of 1 and exit ($n-$ans iterations) :

for($x = $n; $x >= 1; $x--)
{
    if('$x is factor')
        if('$x is prime')
            break;
}

Then, because you are not looking for $n or 1 or 2 or 3, I would exclude them all ($n-$ans-4 iterations) :

for($x = $n-1; $x > 1; $x--)
{
    if('$x is factor')
        if('$x is prime')
            break;
}

Then, you are looking for a factor $x, such as $x1*$x2 = $n, which implies that if $x2 != 1 && $x2 <= sqrt($n) and $x2 is a factor, $x1 = $n/$x2 is a factor too that is larger than $x2 (sqrt($n)-$n/$ans-1 < 775146 iterations). Note that either or both $x1 and $x2 can be prime. Also note that floor() is because we are working with integers and (int) is for PHP7+ compatibility :

for($x1 = (int)floor(sqrt($n)); $x1 > 3; $x2++)
{
    if('$x1 is not a factor')
        continue;
    $x2 = $n/$x1;
    if('$x1 is prime')
        break;
    if('$x2 is prime')
        break;
}

There are ways to do better but since we switched from 600G to 775K it should be enough.

Second loop : $x/2 iterations

Loops in loops are the first thing to resolve when optimizing code. If you loop from 1 to 1000 in a loop from 1 to 1000, that is 1000000 iterations ; in your case it is a bit more complicated to evaluate but I think it is close to $n*$n/2 = 633457474756096856 iterations (!). with the first loop reviewed, is is close to 775146*775146/2 = 300425660658 iterations = 300G iterations : better but still huge !

First thing to do is to break on the first $y != 1 found, if $x1 is not a prime number you do not need to find all its factors (iterations are hard to evaluate but get in mind that all $x1 with factors of 2 and 3 gets their loop reduced from $x1/2 to 2 or 3) :

for($y = 1; $y < $x1/2; $y++)
{
    if($x1 % $y == 0)
    {
        $first_factor = $y;
        break;
    }
}

Then instead of doing $x1/2 do sqrt($x1) as in the loop 1 optimisations :

$first_factor = null;
for($y = (int)floor(sqrt($x)); $y > 1; $y--)
{
    if($x % $y == 0)
    {
        $first_factor = $y;
        break;
    }
}
if(is_null($first_factor))
{
    $ans = $x;
    break;
}

I personaly won't but you can do a faster prime check implementing first one hundred (or so) prime numbers and testing them for factor of $y first.

Code review

Please use functions, you will have a light performance loss due to internal PHP stack behavior but your code will be much cleaner and reusable (for the next Project Euler problems...).

Adjusting all the code gives you something running under 100ms : https://3v4l.org/jXd3E

function greatest_prime($n)
{
    for($x1 = (int)floor(sqrt($n)); $x1 > 3; $x1--)
    {
        if($n % $x1 != 0)
            continue;
        $x2 = $n/$x1;
        if(is_prime($x1))
            return $x1;
        if(is_prime($x2))
            return $x2;
    }
}
function is_prime($x)
{
    for($y = (int)floor(sqrt($x)); $y > 1; $y--)
        if($x % $y == 0)
            return false;
    return true;
}
var_dump(greatest_prime(600851475143));