Verwenden Sie ein Skript, um Primzahlen in PHP zu finden

In der Informatik bezeichnet eine Primzahl eine positive ganze Zahl, die nur durch 1 und sich selbst teilbar ist. Primzahlen können in Bereichen wie Verschlüsselung, mathematischer Ableitung und Algorithmusoptimierung verwendet werden. In praktischen Anwendungen ist der Algorithmus zum Finden von Primzahlen auch einer der sehr wichtigen Wissenspunkte. Heute werden wir diskutieren, wie man Skripte in PHP verwendet, um Primzahlen zu finden.

1. Screening-Methode

Die Screening-Methode ist ein klassischer Algorithmus zum Finden von Primzahlen. Ihre Kernidee besteht darin, kontinuierlich Zahlen herauszufiltern, die keine Primzahlen sind, und am Ende bleibt eine Primzahl übrig. Die spezifischen Schritte sind wie folgt:

1. Initialisieren Sie ein Primzahl-Array $prime = array() und geben Sie Zahlen von 2 bis n (n ist der erforderliche Bereich) hinein.
2. Bestimmen Sie für die Zahl 2~sqrt(n) (sqrt(n) stellt die Quadratwurzel von n dar), ob es sich wiederum um eine Primzahl handelt. Wenn ja, entfernen Sie deren Vielfache aus dem Primzahlenarray.
3. Nachdem die Schleife endet, sind die verbleibenden Zahlen im Primzahlenarray alle Primzahlen.

Der Implementierungscode lautet wie folgt:

function sieve($n) {
    $prime = array();
    for($i = 2; $i <= $n; ++$i) {
        $prime[$i] = true;
    }
    for($i = 2; $i <= sqrt($n); ++$i) {
        if($prime[$i]) {
            for($j = $i*$i; $j <= $n; $j += $i) {
                $prime[$j] = false;
            }
        }
    }
    return array_keys(array_filter($prime));
}

2. Der kleine Satz von Fermat

Der kleine Satz von Fermat ist ein wichtiger Satz der Zahlentheorie, der verwendet werden kann, um zu bestimmen, ob eine Zahl eine Primzahl ist. Fermats kleiner Satz wird wie folgt ausgedrückt: Wenn p eine Primzahl und a eine beliebige ganze Zahl ist, dann ist a^(p-1)≡1(mod p).

Die spezifischen Schritte sind wie folgt:

1. Wählen Sie zufällig eine Zahl a aus und bestimmen Sie, ob a und n zueinander prim sind. Wenn sie nicht zueinander prim sind, geben Sie direkt false zurück.
2. Berechnen Sie den Wert von a^(n-1) mod n. Wenn er nicht gleich 1 ist, geben Sie false zurück.
3. Wenn nach vielen Tests die beiden oben genannten Bedingungen erfüllt sind, ist n wahrscheinlich eine Primzahl.

Der Implementierungscode lautet wie folgt:

function is_prime($n) {
    if($n <= 1) {
        return false;
    }
    for($i = 0; $i < 10; ++$i) {
        $a = rand(1, $n-1);
        if(gcd($a, $n) != 1) {
            return false;
        }
        if(mod_pow($a, $n-1, $n) != 1) {
            return false;
        }
    }
    return true;
}

function gcd($a, $b) {
    return ($b == 0) ? $a : gcd($b, $a%$b);
}

function mod_pow($base, $exp, $modulus) {
    $result = 1;
    while($exp > 0) {
        if($exp % 2 == 1) {
            $result = ($result * $base) % $modulus;
        }
        $exp = $exp >> 1;
        $base = ($base * $base) % $modulus;
    }
    return $result;
}

Die oben genannten sind zwei Methoden zum Finden von Primzahlen mithilfe von Skripten in PHP. Es ist zu beachten, dass die Screening-Methode bei der Lösung eines großen Bereichs von Primzahlen häufig effizienter ist als der kleine Satz von Fermat.

Das obige ist der detaillierte Inhalt vonVerwenden Sie ein Skript, um Primzahlen in PHP zu finden. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!