optimaler Algorithmus zum Auffinden eindeutiger Teiler

Ich habe nur an ein Problem gedacht, das nicht sehr schwer zu sein scheint, aber wenn wir daran denken, es optimal zu machen, wird es zu einem ziemlich guten Problem. Das Problem ist: Wir haben eine Liste (Array) von Zahlen und eine Nummer N erhalten. Wir müssen alle Teiler von N finden, die keine zur Liste gehörende Nummer teilen. Ich habe es mit brachialer Gewalt und ein wenig effizienter Herangehensweise gelöst (aber nicht mit der besten). Ich suche also nach einem Ansatz, der am besten zur Lösung dieses Problems geeignet ist. Alles ist in Ganzzahlen (keine Gleitkommazahlen) ausgedrückt. Jede Idee wird geschätzt.

Mein Ansatz ist, dass ich zuerst alle Teiler der Zahl N finde (ohne Overhead). Dann sortiere ich die Liste und die Teiler in umgekehrter Reihenfolge (getrennt). Nun überprüfe ich für jeden Divisor D, ob er eine Zahl in der Liste teilt (beginnend mit dem höchsten Element bis zu einem Element, das> = Divisor D ist). Wenn es sich teilt, müssen sich auch alle Teiler von D teilen. Dann entferne ich die Elemente aus der Liste der Teiler, die auch die Teiler von D sind (man kann sich vorstellen, dass die Schnittmenge entfernt wird). Letztendlich ist also das linke Array von Teilern das erforderliche Array (gemäß meinem Ansatz). Wenn jemand einen Fehler oder eine mangelnde Effizienz in meinem Ansatz feststellen kann, wird dies geschätzt. Der maximale Wert, der in der Liste vorhanden sein kann, ist 10 ^ 18.

Mein bisheriger Versuch in 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>

Antworten auf die Frage(1)

Ihre Antwort auf die Frage