NB Premier Fermé

Question

Bonjour,
je veux créer une fonction récursive ( algorithme ) qui permet de vérifier si un entier N est premier ou non.
mon prof nous a proposé une correction mais j'arrive pas la comprendre :
Fonction Premier ( d, n : entier ): EntierDébut    Si d <= ( (n div 2) + 1) Alors           Si n Mod d # 0 Alors                 Premier <-- Premier (d+1, n)          Sinon                 Premier <-- vrai           Fin Si     Sinon          Premier <-- faux    Fin SiFin
J'ai pas compris, à quoi sert la variable d, on prend par exemple d = 4 et n= 5
dans ce cas d=4 > (5 div 2) + 1 =3 donc premier condition n'est pas vérifiée et Premier <-- faux
or 5 est un nombre premier...
qui peut m'expliquer SVP.

Nessdarth · Answer

Bonjour, 
d semble être le diviseur.
Pour vérifier si un nombre est premier, il ne doit être divisible que par 1 et lui-même.
Donc la fonction va vérifier que le nombre n'est pas divisible par des nombres entre 2 et n-1
A l'appel de la fonction, à sa 1ere occurence, d devrait être égale à 2.
Donc pour 5, on va vérifier pour les diviseurs 2, 3 et 4, mais on sait aussi qu'on n'est pas obligé de vérifier tous les diviseurs allant jusqu'à n-1, on peut se contenter de la première moitié du groupe de diviseurs.
Par exemple pour l'entier 7, on peut se contenter de vérifier pour 2, 3 et 4, à ce stade inutile de vérifier pour 5 et 6 qui sont dans le 2eme groupe de diviseurs.
En tout cas c'est ce que semble dire la ligne d <= ( (n div 2) + 1)
Après je ne sais pas si cette fonction marche réellement

NB Premier

1 réponse

Discussions similaires