Publié le 27/05/2018
Auteur Fobec
Réseaux sociaux
0 partages
0 tweets
0 plus
0 commentaires

Verificateur de nombres premiers

De nos jours, la recherche de nombre premier est devenue une opération primordiale et que l'on utilise au quotidien. A la base de la cryptographie asymétrique (RSA), les nombres premiers servent de clés publiques et privés dans le chiffrement par exemple dans les communications https sur internet.

Arithmétique et définition

Définition: un nombre premier est un entier naturel qui ne peut être divisé que par 1 et lui-même. Concrètement, les dix premiers sont: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Depuis l'Antiquité et probablement depuis plus longtemps, les hommes sont fascinés par ces nombres. En effet, que ce soit Euclide, Marin Mersenne ou encore Leonhard Euler, à chaque fois les mathématiciens découvrent de nouvelles propriétés aux nombres premiers. Ce que l'on sait:
1. il existe une infinité de nombres premiers,
2. tout nombre pair peut s'écrire comme somme de deux nombres premiers,
3. il n'existe aucune loi mathématique qui détermine leur apparition dans la suite des entiers.

A ce jour, le plus grand nombre premier découvert comporte 23 millions de chiffres !

Fonction de recherche des nombres premiers

A partir des propriétés vues précédemment, voyons comment coder une p'tite fonction pour trouver les nombres premiers dans l'intervalle 0 à 100.
La technique utilisée dans la fonction PHP est de diviser un nombre par tous ceux qui le précèdent. Si le quotient de la division est différent de zéro, alors le nombre n'est pas un nombre premier.

<?php
/**
 * Déterminer si un nombre est premier
 * @param int $number nombre à tester
 * @return boolean
 */
function isPrime($number) {
    //boucle de 2 au nombre à tester
    for ($i = 2; $i < $number; $i++) {
        //test du qutotien de la division
        if ($number % $i == 0) {
            return FALSE;
        }
    }
 
    //Aucun diviseur trouvé, c'est un nombre permier
    return TRUE;
}
 
// boucle de 0 à 99
echo '<br>Nombre premier de 0 à 100: ';
for ($i = 3; $i < 100; $i++) {
    if (isPrime($i)) {
        echo $i.' ';
    }
}

Résultat des 100 premiers nombres premiers
Nombre premier de 0 à 100: 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97


Lorsque le nombre n'est pas trop grand, la fonction ci-dessus fonctionne bien, c-a-d tester tous les diviseurs possibles.

Plus les nombres deviennent grands, plus le nombre de tests à effectuer augmente. Ainsi, les algorithmes utilisant les propriétés des nombres premiers existent. Pour ceux que ça intéresse voici quelques tests de sa primalité qui ont été découverts: test de Fermat, test de Miller-Rabin, ...
A ce que j'ai compris, le nombre de test peut être réduit pour déterminer la distribution des nombres premiers en factorisant et en décomposant les nombres. Si un mathématicien passe par ici, ce serait sympa de nous expliquer un peu plus en détail ces algo.

Ajouter un commentaire

Les champs marqués d'un * sont obligatoires, les adresses emails se sont pas publiées.

A lire aussi

Réseaux sociaux
Présentation de l'article
Catégorie
php5 - script
Mise a jour
27/05/2018
Visualisation
vu 1425 fois
Public
Internaute
Auteur de la publication
Fobec
Admin
Auteur de 264 articles
|BIO_PSEUDO|
Commentaires récents

Publié par robbie dans tuto

desole pour le message en multiple j'ai eu un ptit beug

Publié par pgts09 dans tuto

Bonjour,
Felicitations pour ce tuto simple, et qui semble repondre exactement ce que je cherchais !
Malheureusement je n'arrive pas faire fonctionner, voici ce que donne mon essai : J'ai pourt...

Publié par piranhas dans java

bonjour, je veux te signaler que la piece jointe est fausse car il n\'y pas de liaison entre le modele et la vue, toutes le information passe par le controlleur.

Publié par troops28 dans CMS

C un truc qui va plaire ca ;) enfin j'espere
En ajoutant :
if ColWidths[i] < Canvas.TextWidth(strTemp) then ColWidths[i] := Canvas.TextWidth(strTemp)+10;

Dans la procedure LoadStr...

Publié par romainN dans tuto

Bonjour,

Super tuto bravo! Je suis sur Wordpress 3.5 et 1and1 et la ligne HTML que je dois modifier est prsente dans plusieurs php et elle comprend des echo:

echo \\ dans le fichier wp-...