Déterminer si un entier P est un nombre premier de Germain

Durant cette période de confinement en prévention du covid-19, les gens se livre à divers activités de divertissement pendant le temps qu’ils ne sont pas en télé travail où en face de la télé.

Dr Elkaïoum m’kouboi a créé le groupe Facebook Matheux confinés dans lequel les plus matheux se livrent à des énigmes mathématiques et nous autres intervenons de temps à autres quand ça parle de code.

Le dernier petit jeu auquel je me suis livré était de coder un algorithme qui permet de déterminer si un entier P est un nombre premier de Germain. je vous partage ici mon code.

Pour rappel un nombre premier P est appelé nombre premier de Germain si 2P + 1 est aussi un nombre premier. Ci-dessous mon code PHP qui permet de vérifier cela:

function isPrime($nb){ 
    if ($nb == 1) 
    return 0; 
    for ($i = 2; $i <= $nb/2; $i++){ 
        if ($nb % $i == 0) 
            return 0; 
    } 
    return 1; 
} 

function isGermainPrime($nb) {
    $a = isPrime($nb);
    $b = isPrime(2 * $nb + 1);
  
  echo ($a && $b) ? $nb." Est un nb premier germain" : $nb." n'est pas un nb premier germain";
}

La fonction « isPrime » permet, comme son nom l’indique, de vérifier si un nombre donné est premier. Et la deuxième foncion « isGermainPrime » permet ensuite de vérifier P puis 2p+1 et si les deux nombres sont premier alors P est bien un nombre premier de Germain.

Imaginez que nous voulions déterminer si le nombre 2 000 001 est un premier de Germain ! cela nécessitera 1 000 000 d’instruction au code ci-dessus. C’est la remarque soulevé par Dr Elkaïoum. Quel solution pour réduire ce nombre d’instruction ?

il suffit de se limiter $i à la racine carré de $nb et bingo ! le nombre d’instruction nécessaire devient alors sqrt(n2) = 1414. Le boucle fort dans la première fonction devient alors:

for ($i = 2; $i <= sqrt($nb); $i++) { 
        if ($nb % $i == 0) 
            return 0; 
    } 

J’espère que ceci t’as été utile sinon bon confinement où bonne journée si je confinement est passé.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *