effiziente Art und Weise einzigartig Teilern

Question

Mögliche Duplizieren zu finden:
optimal algorithm for finding unique divisors

ich vor diese Frage gestellt haben, aber das Konto ist jetzt nicht zugänglich, so frage ich es wieder meine zeigt Aufwand diesmal.

Gegeben einer Liste (Array) von Zahlen und einer Zahl N, finde alle Teiler von N, die keine Zahl teilen, die zu der Liste gehört. Ich habe es mit einer rohen Gewalt und ein wenig effizienten Ansatz gelöst (aber nicht der beste). Also suche ich nach einem Ansatz, der das beste ist, um diese Art von Problem zu lösen. Alles ist in Integer-Zahlen ausgedrückt (keine Fließkommazahlen).

Mein Ansatz ist, dass ich zuerst alle Teiler der Zahl N (ohne Overhead) finde. Dann sortiere ich die Liste und die Teiler in umgekehrter Reihenfolge (getrennt). Jetzt prüfe ich für jeden Teiler D, ob er irgendeine Zahl in der Liste teilt (beginnend mit dem höchsten Element bis zu einem Element, das> = der Teiler D ist). Wenn es sich teilt, müssen sich auch alle Teiler von D teilen. Dann entferne ich diese Elemente aus der Liste der Teiler, die auch die Teiler von D sind (kann man sich so vorstellen, als würde man die Kreuzung entfernen). Letztendlich ist das linke Array von Divisoren das erforderliche Array (nach meinem Ansatz). Wenn jemand einen Fehler oder einen Mangel an Effizienz in meinem Ansatz feststellen kann, wird dies geschätzt. Der Maximalwert, der in der Liste vorhanden sein kann, ist 10^18.

Ich habe es in PHP implementiert. Ich stelle meinen Code unten zur Verfügung. Bitte ignorieren Sie die Kommentare.

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; 
} 

Answer 1

Sie können diese PHP implementation of the sieve of Eratosthenes verwenden.

Und auch this.

Und this.

Werfen Sie einen Blick auf this question.