оптимальный алгоритм поиска уникальных делителей
Я просто думал о проблеме, которая не кажется слишком сложной, но когда мы думаем сделать это оптимально, это становится довольно хорошей проблемой. Проблема состоит в том, что нам дали список (массив) чисел и число 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>