Самый большой простой фактор с php - PullRequest
Новая
       4

Самый большой простой фактор с php

2 голосов
/ 19 мая 2010

Я написал программу на 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;

Ответы [ 3 ]

7 голосов
/ 19 мая 2010

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

Вы не сможете работать с целыми числами, превышающими это значение в PHP.

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

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

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

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

6 голосов
/ 19 мая 2010

Вы должны прочитать о Первичном тестировании и Просеивание .

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

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

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

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

0 голосов
/ 19 мая 2010

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

...