PHP-CLI générateur de nombres premiers

ATTENTION Ce code n'a pas pour vocation à être utilisé dans un navigateur. Si vous augmentez considérablement la variable $nbr utilisez plutôt PHP en ligne de commande (PHP-CLI).

Nombres premiers

Téléchargez ici un gzip des 3.001.134 nombres premiers de 2 à 49.999.991 générés avec ce code.

<?php
# ----------------------------------------------------------- #
#               REGLE POUR LES NOMBRES PREMIERS               #
#   Si n n'est pas premier, alors il a au moins un diviseur   #
#   PREMIER inférieur ou égal à sqrt(n) et différent de 1     #
#   Si n n'a pas de diviseur inférieur ou égal à sqrt(n) et   #
#   qu'il est différent de 1 alors n est premier.             #
# ----------------------------------------------------------- #

// le plus grand nombre à tester au delà du-quel le programme s'arrêtera.
$nbr = 5000; 

$premiers = array(2,3); // tableau des nombres premiers déclaré avec les deux premiers

$fichier = fopen('premiers.txt', 'a+'); // fichier qui contiendra les résultats

fputs($fichier, "2\n3\n"); // on va pas oublier ces deux là

// on commence à 5 qui est le nombre premier suivant 3
// on incrémente de 2 pour rester sur des nombres impairs et ainsi éviter à la 
// fonction de s’exécuter sur les nombres pairs qui ne sont évidement pas premiers
for ($n=5; $n < $nbr; $n+=2) {
    // Si $n n'est pas premier, alors il a au moins un diviseur inférieur ou égal à sqrt(n) sauf 1
    $rn = sqrt($n);
    // construction d'un tableau $rp de tous les nombres premiers inférieurs à $rn
    $rp = array();
    foreach ($premiers as $value) {
        if($value <= $rn) $rp[] = $value;
        else break;
    }
    // chercher un diviseurs de $n
    // si aucun diviseur n'est trouvé en fin de boucle alors $n est premier
    foreach ($rp as $value) {
        $candidat = 1;
        if($n % $value == 0){
            // $n à $value comme diviseur il n'est donc pas premier
            // $candidat passe à zero et on quitte la boucle foreach
            $candidat = 0;
            break;
        }
    }

        // si $candidat vaut toujours 1 on est en présence d'un nombre premier
        // on incrémente le tableau et le fichier
    if($candidat > 0) {
        $premiers[] = $n;
        fputs($fichier, $n."\n");
    }
}
fclose($fichier);

Une fois lancé il est possible de suivre en temps réel l'avancement grâce à la commande tail

$ tail -f premiers.txt
23-Mar-2024
^