Właśnie myślałem o problemie, który nie wydaje się być zbyt trudny, ale kiedy myślimy o zrobieniu tego optymalnie, staje się to całkiem dobrym problemem. Problem polega na tym, że otrzymaliśmy listę (tablicę) liczb i liczbę N. Musimy znaleźć wszystkie dzielniki N, które nie dzielą żadnej liczby należącej do listy. Rozwiązałem go brutalną siłą i trochę skutecznym podejściem (ale nie najlepszym). Więc szukam podejścia, które mogłoby być najlepsze w rozwiązywaniu tego rodzaju problemów. Wszystko jest w kategoriach liczb całkowitych (bez punktów zmiennoprzecinkowych). Każdy pomysł jest doceniany.

Moje podejście do tego polega na tym, że najpierw znajduję wszystkie dzielniki liczby N (bez żadnych kosztów ogólnych). Następnie sortuję listę i dzielniki w odwrotnej kolejności (oddzielnie). Teraz, dla każdego dzielnika D, sprawdzam, czy dzieli on dowolną liczbę na liście (zaczynając od najwyższego elementu do elementu, który jest> = dzielnik D). Jeśli się dzieli, wszystkie dzielniki D muszą również się dzielić. Następnie usuwam te elementy z listy dzielników, które są również dzielnikami D (można je traktować jako usuwanie przecięcia). Ostatecznie lewa tablica dzielników jest wymaganą tablicą (zgodnie z moim podejściem). Jeśli ktoś może wskazać jakąkolwiek wadę lub brak skuteczności w moim podejściu, jest to doceniane. Maksymalna wartość, która może być obecna na liście, to 10 ^ 18.

Moja dotychczasowa próba w 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>