оптимальный алгоритм поиска уникальных делителей

Я просто думал о проблеме, которая не кажется слишком сложной, но когда мы думаем сделать это оптимально, это становится довольно хорошей проблемой. Проблема состоит в том, что нам дали список (массив) чисел и число N. Нам нужно найти все делители числа N, которые не делят любое число, принадлежащее списку. Я решил это грубой силой и немного эффективным подходом (но не лучшим). Итак, я ищу подход, который мог бы быть лучшим в решении такого рода проблем. Все в терминах целых чисел (без чисел с плавающей запятой). Каждая идея ценится.

Мой подход заключается в том, что я сначала нахожу все делители числа N (без каких-либо накладных расходов). Затем я сортирую список и делители в обратном порядке (отдельно). Теперь для каждого делителя D я проверяю, делит ли он какое-либо число в списке (начиная с самого высокого элемента до элемента, который является & gt; = делителем D). Если он делит, то все делители D также должны делиться. Затем я удаляю те элементы из списка делителей, которые также являются делителями D (можно рассматривать как удаление пересечения). Итак, в конечном итоге левый массив делителей является требуемым массивом (согласно моему подходу). Если кто-то может указать на какую-либо ошибку или отсутствие эффективности в моем подходе, это приветствуется. Максимальное значение, которое может присутствовать в списке, составляет 10 ^ 18.

Моя попытка до сих пор в PHP:

<code>while($div=each($divisors))
{
$i=0;
$divisor=$div['key'];
//echo "divisor is $divisor\n";
while((int)$unfriendly[$i]>=$divisor)
{//echo "aya\n";
    if(!((int)bcmod($unfriendly[$i],$divisor)))
    {//echo "ayeea\n";
        $divisors_of_divisor=divisors_of_a_number($divisor);
        //print_r($divisors_of_divisor);
        //print_r($divisors);
        foreach($divisors_of_divisor as $d)
        unset($divisors[$d]);
        //print_r($divisors);
        break;
    }
    ++$i;
}
 }
echo sizeof($divisors);
function divisors_of_a_number($n)//returns all the divisors of a number in an unsorted array
{
$i=1;
$s=sqrt($n);
while($i<=$s)
{
if(!($n%$i))
{
    $a[]=$i;
    if($i!=$s)
    $a[]=$n/$i;
}
++$i;
}
return $a;
}
function divisors_of_a_number_as_keys_of_array($n)//returns all the divisors of a number in an unsorted array as keys
{
$i=1;
$s=sqrt($n);
while($i<=$s)
{
if(!($n%$i))
{
    $a[$i]=1;
    //if($i!=$s)
    $a[$n/$i]=1;
}
++$i;
}
return $a;
}
</code>
 james08 апр. 2012 г., 09:46
Не могли бы вы показать свои усилия здесь.

Ответы на вопрос(1)

Решение Вопроса

Одна очевидная оптимизация заключается в следующем - сделатьсито из эратосфена Фаторизировать все числа до значения, которое вы знаете, выше, чем любой из перечисленных вами в списке. Теперь вы можете перебирать все факторы данного числа из этого списка.

Что вы делаете дальше: для каждого числа из списка и каждого из его простых факторов p вы должны делить N на p, пока оно не будет делиться на него. После того, как вы это сделаете, все делители, которые вы ищете, являются делителями оставшегося числа.

Надеюсь это поможет.

Ваш ответ на вопрос