Trois façons de déterminer si un nombre est premier en PHP-tutoriel php-php.cn

Trois façons de déterminer si un nombre est premier en PHP

不言

Libérer： 2023-04-04 09:18:02

avant

5271 Les gens l'ont consulté

Cet article vous propose trois méthodes pour déterminer si un nombre est premier en PHP. Il a une certaine valeur de référence. J'espère que cela vous sera utile.

Définition des nombres premiers

Les nombres premiers sont aussi appelés nombres premiers. Un nombre naturel supérieur à 1 qui ne peut être divisé en d’autres nombres naturels sauf 1 et lui-même est appelé nombre premier, sinon il est appelé nombre composé ;

Idée de mise en œuvre

Parcourez tous les nombres alternatifs possibles, puis comparez-les avec des entiers inférieurs au nombre du milieu et supérieurs ou égaux à 2. S'il peut être divisé en nombres entiers, c'est certainement ce n'est pas un nombre premier. Au contraire, ce sont des nombres premiers.

Le premier algorithme

C'est aussi le plus susceptible de venir à l'esprit en premier, qui consiste à comparer directement avec le nombre du milieu des alternatives. Le code source de l'algorithme est le suivant :

/**
 * 获取所有的质数
 * @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;
}

Copier après la connexion

### Le deuxième algorithme

Sérieusement parlant, ce n'est pas un autre algorithme, c'est juste une légère optimisation du premier et l'optimisation du nombre maximum au milieu. pour affiner la plage de comparaison. Algorithme Le code source est le suivant :

/**
 * 获取所有的质数
 * @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;
}

Copier après la connexion

Le troisième algorithme

C'est aussi une optimisation pour le deuxième type, c'est-à-dire tous les nombres qui ne le sont pas. Les nombres premiers peuvent être directement supprimés du tableau complet. Code source de l'algorithme Comme suit :

/**
 * 获取所有的质数
 * @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);
}

Copier après la connexion

Méthode d'utilisation

Par exemple, recherchez tous les nombres premiers de 1 à 100

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

Copier après la connexion

Autre exemple, trouver tous les nombres premiers dans le tableau spécifié

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

Copier après la connexion

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!