Нахождение наибольшего простого делителя?

Question

[adun3]

Добрый день! хочу найти наибольший простой делитель числа 600851475143.
как делаем? ищем все простые числа до корня(600851475143), т.е. до 775147, а потом проверяем делимость 600851475143 на эти простые числа. но почему то выдает 3 и 29(и то и то не делитель). подскажите пожалуйста, где туплю, я только начал прогать, если что.

define("LIMIT",775147);
    define("SQRT_LIMIT",floor(sqrt(LIMIT)));
    
    $S = str_repeat("\1", LIMIT+1);

    for($i=2;$i<=SQRT_LIMIT;$i++){
    if($S[$i]==="\1"){
        for($j=$i*$i; $j<=LIMIT; $j+=$i){
            $S[$j]="\0";
            }
        }
    }
    for($i=2;$i<=LIMIT;$i++)
    {
        if($S[$i]=="\1" && (600851475143 % $i) == 0)
        {
            echo $i.' ';
        }
    }
        ?>

Answer 1

[Sumor]

Число 600851475143 превышает 4 байта.
Если брать только 4 байта от этого числа, то получается число -443946297, которое как раз и делится на 3 и на 29.
То есть у вас программа работает только с четырёхбайтными числами.

Answer 2

[brutal_lobster]

Хм. str_repeat полностью сбивает с толку - это очень интересное решение) но совершенно не адекватное.
Для хранения списка простых чисел - используйте массив (array) этих самых чисел :)

Лучше вооружитесь книжкой по языку и возьмите самый тупой алгоритм разложения на простые множители - тот в котором делим (если делится, конечно) число на все числа начиная с 2, пока оно не станет равным 1.

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

Comments

[adun3]

я его в инете нашел, хрет мало ресурсов, находит нормально. исходное число большое чтобы самым простым алгоритмом его проверять.

Answer 3

[adun3]

for($i=2;$i<=LIMIT;$i++)
{
$ostatok = bcmod('600851475143', $i);

if($S[$i]=="\1" && $ostatok == 0)
{
echo $i.' ';
}

вообще хочется 2 пальца от своего алгоритма засунуть в рот, но ничего, главное все нашлось :)