Wie kann eine PHP-Funktion effizient bestimmen, ob eine Zahl eine Primzahl ist?

Eine Formel zum Finden von Primzahlen in einer Schleife

Diese Frage versucht, Primzahlen mithilfe eines Schleifenmechanismus zu identifizieren. Konkret zielt die Frage darauf ab, eine PHP-Funktion zu erstellen, um Primzahlen effizient zu finden.

Um den Prozess zu verstehen, führen wir das Konzept der Primzahlen ein. Primzahlen sind ganze Zahlen größer als 1, die durch keine andere ganze Zahl außer 1 und sich selbst teilbar sind.

Diese Definition schlägt eine einfache Möglichkeit zur Prüfung auf Primalität vor: Teilen Sie die Zahl durch alle ganzen Zahlen von 2 bis zum Quadrat Wurzel der Zahl. Wenn eine dieser Divisionen einen Rest hat, ist die Zahl eine Primzahl.

Die in der Antwort auf die Frage bereitgestellte PHP-Funktion folgt diesem Konzept:

<code class="php">function isPrime($num) {
    //1 is not prime. See: http://en.wikipedia.org/wiki/Prime_number#Primality_of_one
    if($num == 1)
        return false;

    //2 is prime (the only even number that is prime)
    if($num == 2)
        return true;

    /**
     * if the number is divisible by two, then it's not prime and it's no longer
     * needed to check other even numbers
     */
    if($num % 2 == 0) {
        return false;
    }

    /**
     * Checks the odd numbers. If any of them is a factor, then it returns false.
     * The sqrt can be an aproximation, hence just for the sake of
     * security, one rounds it to the next highest integer value.
     */
    $ceil = ceil(sqrt($num));
    for($i = 3; $i <= $ceil; $i = $i + 2) {
        if($num % $i == 0)
            return false;
    }

    return true;
}</code>

Diese Funktion verwendet ein Array zum Speichern der Faktoren der Zahl und prüft die Reste der Divisionen. Wenn ein Rest Null ist, weist dies auf das Vorhandensein eines Faktors hin, wodurch die Zahl keine Primzahl ist. Wenn jedoch keine Faktoren gefunden werden, gilt die Zahl als Primzahl.

Das obige ist der detaillierte Inhalt vonWie kann eine PHP-Funktion effizient bestimmen, ob eine Zahl eine Primzahl ist?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!