Les Nombres Premiers Fermé

Question

Bonjour, 

Est Ce Que quelqu'un pourrai m'aidez a resoudre ce probleme : " ecrivez un sous programme si un entier plus grand que 1 est premiers ou non "

Merci :)

Configuration: Windows 7 / Internet Explorer 8.0 / Langage Pascal

Doctor C · Answer

Un nombre premier est un nombre qui ne se divise que par 1 et par lui-même.

Donc, étant un nombre n, tu pourrais faire une boucle de 1+1 à n -1 et si aucune division n/i ne donne zéro, n est premier.

Ex:

int n = 13;
Bool estPremier = vrai;

Pour (i = 1+1 ; i < n ; i++)
    Si n modulo i == 0 Alors
        estPremier = faux; 
        break;

Bon, je suis malade présentement et mon cerveau n'est pas tout à fait en pleine forme mais je croix que ce code fonctionne. Ou du moins la logique.

Il manque des trucs du genre (si n>1) etc. mais ce sont des détails que tu peux corriger.

KX · Answer

Remarque
On peut gagner la moitié du nombre de calculs en ne considérant que les nombres impairs, les nombres pairs n'étant pas premiers (excepté 2).
Et pour enlever encore plus de calculs inutiles, il faut s'arrêter à la racine carrée de n.
En effet il ne peut exister de diviseur de n supérieur à sqrt(n) excepté n lui même.

Du coup si n est premier on le saura après 2+sqrt(n)/2 calculs (nombre de tests if).
Avant on aurait fait n-2 calculs en testant toutes les valeurs de 2 jusqu'à n-1.

Exemple
n = 2^31-1 (c'est le plus grand integer en Pascal, et il est premier)
Avant on aurait fait 2 147 483 645 calculs pour dire que ce nombre est premier, alors qu'ici je n'en ai besoin que de 23 171 pour arriver à la même conclusion.

function estPremier(n:integer):boolean;
var i,r:integer;
begin
     if (n < 2)  // 0 et 1 ne sont pas premiers
        then exit(false);

     if (n mod 2 = 0) // 2 est le seul nombre pair premier
        then exit(n=2);

     i:=3;
     r:=trunc(sqrt(real(n))); // r = racine carrée de n

     while (i <= r) do
        if (n mod i = 0)    // si i divise n
           then exit(false) // n n'est pas premier : n = i*(n/i)
           else i:=i+2;     // on considère le nombre impair suivant

     exit(true);
end;

VAR i:integer;
BEGIN
     for i:=0 to 100 do
         if estPremier(i)
            then writeln(i);
readln;
END.

Les Nombres Premiers

2 réponses

Discussions similaires