Utiliser un script pour trouver des nombres premiers en php

En informatique, un nombre premier fait référence à un entier positif qui n'est divisible que par 1 et par lui-même. Les nombres premiers peuvent être utilisés dans des domaines tels que le cryptage, la dérivation mathématique et l'optimisation des algorithmes. Dans les applications pratiques, l'algorithme de recherche de nombres premiers est également l'un des points de connaissances très importants. Aujourd'hui, nous allons discuter de la façon d'utiliser des scripts en PHP pour trouver des nombres premiers.

1. Méthode de filtrage

La méthode de filtrage est un algorithme classique pour trouver des nombres premiers. Son idée principale est de filtrer en continu les nombres qui ne sont pas des nombres premiers, et ce qui reste à la fin est un nombre premier. Les étapes spécifiques sont les suivantes :

1. Initialisez un tableau premier $prime = array() et insérez-y des nombres de 2 à n (n est la plage requise).
2. Pour le nombre 2~sqrt(n) (sqrt(n) représente la racine carrée de n), déterminez à votre tour s'il s'agit d'un nombre premier. Si c'est le cas, supprimez ses multiples du tableau de nombres premiers.
3. Une fois la boucle terminée, les nombres restants dans le tableau de nombres premiers sont tous des nombres premiers.

Le code d'implémentation est le suivant :

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. Le petit théorème de Fermat

Le petit théorème de Fermat est un théorème important de la théorie des nombres qui peut être utilisé pour déterminer si un nombre est premier. Le petit théorème de Fermat s'exprime comme suit : Si p est un nombre premier et a est un nombre entier quelconque, alors a^(p-1)≡1(mod p).

Les étapes spécifiques sont les suivantes :

1. Sélectionnez au hasard un nombre a et déterminez si a et n sont premiers entre eux. S'ils ne le sont pas, renvoyez directement false.
2. Calculez la valeur de a^(n-1) mod n, si elle n'est pas égale à 1, renvoyez false.
3. Après de nombreux tests, si les deux conditions ci-dessus sont remplies, alors n est probablement un nombre premier.

Le code d'implémentation est le suivant :

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

Les deux méthodes ci-dessus permettent de trouver des nombres premiers à l'aide de scripts en PHP. Il convient de noter que la méthode de criblage est souvent plus efficace que le petit théorème de Fermat lors de la résolution d'une large gamme de nombres premiers.

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!