CODEWITHSUNDEEP
phpprime-factoring
good_evening
good_evening

Reputation: 21759

The largest prime factor with php

I wrote a program in PHP to find the largest prime factor. I think it is quite optimized, because it loads quite fast. But, there is a problem: it doesn't count the prime factors of very big numbers. Here is the 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;

Upvotes: 2

Views: 3269

Answers (3)

Dolph
Dolph

Reputation: 50690

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.

Upvotes: 7

David
David

Reputation: 7153

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.

Upvotes: 6

Mikulas Dite
Mikulas Dite

Reputation: 7941

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.

Upvotes: 0

Related Questions