Drei Möglichkeiten, um in PHP festzustellen, ob eine Zahl eine Primzahl ist-PHP-Tutorial-php.cn

Drei Möglichkeiten, um in PHP festzustellen, ob eine Zahl eine Primzahl ist

不言

Freigeben： 2023-04-04 09:18:02

nach vorne

5272 Leute haben es durchsucht

Dieser Artikel stellt Ihnen drei Methoden vor, wie Sie feststellen können, ob eine Zahl eine Primzahl ist. Ich hoffe, dass sie für Sie hilfreich ist.

Definition von Primzahlen

Primzahlen werden auch Primzahlen genannt. Eine natürliche Zahl größer als 1, die nicht in andere natürliche Zahlen außer 1 geteilt werden kann und selbst eine Primzahl genannt wird, andernfalls wird sie eine zusammengesetzte Zahl genannt.

Implementierungsidee

Durchlaufen Sie alle möglichen alternativen Zahlen und vergleichen Sie sie dann mit ganzen Zahlen unterhalb der mittleren Zahl und größer oder gleich 2. Wenn es in ganze Zahlen unterteilt werden kann, ist dies definitiv der Fall keine Primzahl, im Gegenteil, es sind Primzahlen.

Der erste Algorithmus

Dies ist auch der erste, der mir zuerst in den Sinn kommt, nämlich der direkte Vergleich mit der mittleren Anzahl der Alternativen. Der Quellcode des Algorithmus lautet wie folgt:

/**
 * 获取所有的质数
 * @param array $arr
 * @return array
 */
function get_prime_number($arr = []) {
    // 质数数组
    $primeArr = [];
    // 循环所有备选数
    foreach ($arr as $value) {
        // 备选数和备选数的中间数以下的数字整除比较
        for ($i = 2; $i <= floor($value / 2); $i++) {
            // 能够整除，则不是质数，退出循环
            if ($value % $i == 0) {
                break;
            }
        }
        // 被除数$j比备选数的中间数大的则为质数
        // 这样判断的依据：
        // 假如备选数为质数，则内层的for循环不会break退出，则执行完毕，$i会继续+1，即最后$i = floor($value / 2) + 1
        // 假如备选数不为质数，则内层的for循环遇到整除就会break退出，$i不会继续+1，即最后$i <= floor($value / 2)
        if ($value != 1 && $i > floor($value / 2)) {
            $primeArr[] = $value;
        }
    }
    return $primeArr;
}

Nach dem Login kopieren

## # Der zweite Algorithmus

Im Ernst, dies ist kein weiterer Algorithmus. Es handelt sich lediglich um eine geringfügige Optimierung des ersten und die Optimierung der maximalen Anzahl in der Mitte, um ihn einzugrenzen Der Vergleichsbereich lautet wie folgt:

/**
 * 获取所有的质数
 * @param array $arr
 * @return array
 */
function get_prime_number($arr = []) {
    // 质数数组
    $primeArr = [];
    // 循环所有备选数
    foreach ($arr as $value) {
        // 备选数和备选数的中间数以下的数字整除比较
        for ($i = 2; $i <= floor($value / $i); $i++) {
            // 能够整除，则不是质数，退出循环
            if ($value % $i == 0) {
                break;
            }
        }
        // 被除数$j比备选数的中间数大的则为质数
        // 这样判断的依据：
        // 假如备选数为质数，则内层的for循环不会break退出，则执行完毕，$i会继续+1，即最后$i = floor($value / $i) + 1
        // 假如备选数不为质数，则内层的for循环遇到整除就会break退出且$i不会继续+1，即最后$i <= floor($value / $i)
        if ($value != 1 && $i > floor($value / $i)) {
            $primeArr[] = $value;
        }
    }
    return $primeArr;
}

Nach dem Login kopieren

Der dritte Algorithmus

Dies ist auch eine Optimierung für den zweiten Typ, das heißt, löschen Sie einfach alle Zahlen, die keine Primzahlen sind Zahlen direkt aus dem vollständigen Array. Der Quellcode des Algorithmus lautet wie folgt:

/**
 * 获取所有的质数
 * @param array $arr
 * @return array
 */
function get_prime_number_three($arr = []) {
    // 质数数组
    $primeArr = $arr;
    // 循环所有备选数
    foreach ($primeArr as $key => $value) {
        if ($value == 1) {
            unset($primeArr[$key]);
            continue;
        }
        // 备选数和备选数的中间数以下的数字整除比较
        for ($i = 2; $i <= floor($value / $i); $i++) {
            // 能够整除，则不是质数，从数组中删除且退出循环
            if ($value % $i == 0) {
                unset($primeArr[$key]);
                break;
            }
        }
    }
    // 重置数组索引返回
    return array_values($primeArr);
}

Nach dem Login kopieren

Verwendungsmethode

Suchen Sie beispielsweise alle Primzahlen von 1-100

// 所有备选数数组
$numberArr = range(1, 100, 1);
// 获取备选数中的所有质数
$primeNumberArr = get_prime_number($numberArr);
// 输出打印
print_r($primeNumberArr);

Nach dem Login kopieren

Andere Finden Sie beispielsweise alle Primzahlen im angegebenen Array

// 所有备选数数组
$numberArr = [11, 22, 33, 66, 77, 3, 8, 10, 99];
// 获取备选数中的所有质数
$primeNumberArr = get_prime_number($numberArr);
// 输出打印
print_r($primeNumberArr);

Nach dem Login kopieren

Das obige ist der detaillierte Inhalt vonDrei Möglichkeiten, um in PHP festzustellen, ob eine Zahl eine Primzahl ist. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!