Самый большой простой множитель с php

Я написал программу на PHP для нахождения наибольшего простого множителя. Я думаю, что он достаточно оптимизирован, потому что загружается довольно быстро. Но есть проблема: он не считает простые множители очень больших чисел. Вот программа:

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;

php prime-factoring
person good_evening    schedule 19.05.2010    source источник
comment
я бы переименовал is_even в is_prime и пусть он возвращает false в последней строке функции. Кроме того, вам не нужно включать $i = 1 или $i = $s в этот цикл, вы можете просто вернуть false, если оно делится на любое другое число.   -  person catchmeifyoutry    schedule 19.05.2010

Ответы (3)


arrow_upward
7
arrow_downward

Наибольшее целое число без переполнения в PHP хранится в константе PHP_INT_MAX.

Вы не сможете работать с целыми числами больше этого значения в PHP.

Чтобы увидеть все предопределенные константы PHP, просто используйте:

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

PHP_INT_MAX, вероятно, имеет значение 2,147,483,647.

Для обработки чисел произвольной точности в PHP см. либо GMP или BC Math Расширения PHP.

person Dolph    schedule 19.05.2010

arrow_upward
6
arrow_downward

Вам следует прочитать об Prime-тестировании и Просеивание.

В частности, вам не нужно проверять, является ли каждый из ваших делителей простым.

Что-то вроде следующего будет быстрее.

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

Вы также можете остановить свой внешний цикл, когда $i достигает sqrt($x), и если вы еще не нашли делитель, вы знаете, что $x простое число.

person David    schedule 19.05.2010

arrow_upward
0
arrow_downward

Что ж, у каждого языка есть свои (хотя обычно одинаковые) ограничения, поэтому, если вы превысите этот предел php, вы не сможете подняться выше. Максимальное целое число равно 9E18.

person Mikulas Dite    schedule 19.05.2010
comment
Конечно, вы можете расширить ограничения, просто напишите класс (или найдите библиотеку), который хранит сколь угодно большие числа в виде массивов чисел меньше MAX_INT и предоставляет стандартные операторы для работы с ними. - person tloach; 19.05.2010
comment
См. мой ответ для ссылок на расширения GMP и BC Math, которые обрабатывают сколь угодно большие числа в PHP. - person Dolph; 19.05.2010
comment
То, что вы предлагаете, является хорошим обходным путем. Однако вы не можете превышать заданные ограничения. - person Mikulas Dite; 20.05.2010