problème pour déterminer si un nombre est premier

Version imprimable

Bonjour,

voila mon problème : j'ai monté un petit programme qui me dit si un nombre est premier ou pas. il fonctionne très bien pour des nombres jusqu'à 10 chiffres mais meme les nombre à 10 chiffres ne sont pas tous pris a partir d'environ 3000000000. je sais qu'il s'agit d'un problème de déclaration de variable, mais meme en les métant en long unsigned, ça ne change pas le problème.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
 
int p,x,n;
 
float r;
 
int main()
{
     printf("-----------------------------\nVOTRE NOMBRE EST-IL PREMIER ?\n-----------------------------\n");
     printf("NOMBRE A IDENTIFIER : ");
     scanf("%d", &n);
     r=sqrt(n);
     p=1;
     for(x=2;x<=r;x++)
     {
                      if(n%x == 0)
                      {
                             printf("\nNON, %d N'EST PAS PREMIER", n);
                             p=0;
                             break;
                      }
     }
     if (p == 1)
     {
           printf("\nOUI, %e EST PREMIER", n);
     }
     fflush(stdin);
     getchar();
     return 0;
}

22/01/2007, 01h45
Thierry Chappuis
Salut,

Je ne sais pas quelle la taille d'un entier de type int sur ta machine, mais sur la mienne, une signed int est codé sur 32 bits. Ansi l'entier maximal qu'il m'est possible de stocker dans ta variable n est 2^31 - 1 = 2'147'483'647 < 3'000'000'000.

Sinon, en ce qui concerne ton programme proprement dit:
1. l'usage des variables globales p, x, n, r n'est pas justifié ici (ni justifiable d'ailleurs).
2. la forme de main n'est pas valide. Ecrire int main(void) ou int main(int argc, char *argv[]).
3. L'affichage avec printf("NOMBRE A IDENTIFIER : ") n'est pas garantit à cause du mécanisme de tampon que printf() utilise pour optimiser l'efficacité de l'affichage. Ajouter fflush(stdout);
4. L'usage de scanf est OK ici, mais en ce me concerne, je préfère l'éviter systématiquement.
5. fflush(stdin), c'est strictement INTERDIT avec un flux entrant et cela engendre un comportement indéfini
Thierry
22/01/2007, 01h59
thewho

Bonjour,

Comme l'a déjà dit mujigka, tu te heurtes à la limite de représentation des int sur 32 bits.

Si ton compilateur le supporte, tu peux utiliser des int de 64 bits pour aller plus loin.

Je vois au moins 2 améliorations à faire :

* pour la variable r stockant la racine carrée de ton nombre, il vaut mieux utiliser un int également, la comparaison sera plus rapide

* améliorer la boucle de calcul :
- commencer par éliminer les nombres pairs, sans oublier de traiter le cas = 2, qui est premier.
- puis la boucle devient

Code:

for(x=3;x<=r;x+=2)

tu traites ainsi 2 fois moins de nombres, pour le seul ajout, avant d'entrer dans la boucle, de tester si ton nombre = 2 (il est premier), ou s'il est pair (il n'est pas premier)

merci pour tout ces détails. mais cela ne résoud pas mon poblème.
j'aimerais aller au-dela de 2^31 - 1. et comme je l'ai deja signalé, j'ai déjà essayé de déclarer mes variable comme unsigned long mais sans succès.
pour le compilateur j'utilise dev-c++ qui, je suppose, supporte les int à 64 bits. quoique quand j'essaie une valeur en dessus de 2^31 -1, il m'affiche le message suivant : [Warning] this decimal constant is unsigned only in ISO C90
je dois avouer que je ne comprend pas. HELP
pour l'optimisation de la boucle, j'y avais deja pensé. je vais l'ajouter.
Pour le fflush(stdin) c'est juste à cause du scanf, puisque sans fflush le getchar ne sert à rien et le programme se ferme avant que j'ai pu voir le résultat, alors prière de ne pas en tenir compte, il s'agit la juste d'un petit bricolage maison.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 #include <stdio.h> int p,x,n; float r; int main(void) { printf("-----------------------------\nVOTRE NOMBRE EST-IL PREMIER ?\n-----------------------------\n"); printf("NOMBRE A IDENTIFIER : "); scanf("%d", &n); r=sqrt(n); p=1; if(n%2==0) { printf("\nNON, %d N'EST PAS PREMIER", n); p=0; } else { for(x=3;x<=r;x+=2) { if(n%x == 0) { printf("\nNON, %d N'EST PAS PREMIER", n); p=0; break; } } } if (p == 1) { printf("\nOUI, %e EST PREMIER", n); } fflush(stdin); getchar(); return 0; }

22/01/2007, 08h51
la drogue c'est mal

et avec un double ?
22/01/2007, 10h55
thewho

Bonjour,

DevC++ en soi n'est pas un compilateur, mais une IDE.

Quel compilateur as-tu ?

Pour le type 64 bits, essaye unsigned long long

Citation:

Envoyé par Phils46

merci pour tout ces détails. mais cela ne résoud pas mon poblème.
j'aimerais aller au-dela de 2^31 - 1. et comme je l'ai deja signalé, j'ai déjà essayé de déclarer mes variable comme unsigned long mais sans succès.

Si tu as un compilateur comme gcc 3.x ou plus, pas de probèmes. Sous Windows, la bibliothèque du C est fournie par Microsoft, et printf ne comprend pas le format standard "%lld" ou "%ll". Pas grave, il suffit d'utiliser "%I64d" ou "%I64u".
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <stdio.h> #include <limits.h> #ifdef WIN32 #define LLD "%I64d" #define LLU "%I64u" #else #define LLD "%lld" #define LLU "%llu" #endif int main (void) { printf (LLD"\n", LONG_LONG_MIN); printf (LLD"\n", LONG_LONG_MAX); printf (LLU"\n", ULONG_LONG_MAX); return 0; }
Code:

1 2 3 4 5 6 -9223372036854775808 9223372036854775807 18446744073709551615 Press ENTER to continue.

24/01/2007, 19h12
David.Schris

Bonjour,

Pour ne pas être limité par la taille de tel ou tel type de base, peut-être pourriez-vous utiliser une bibliothèque appropriée (ex. : GMP) ?

Cordialement,
DS.
24/01/2007, 22h12
thewho

Bonjour,

Citation:

Envoyé par David.Schris

Bonjour,

Pour ne pas être limité par la taille de tel ou tel type de base, peut-être pourriez-vous utiliser une bibliothèque appropriée (ex. : GMP) ?

Cordialement,
DS.

C'est une solution.

Je ne l'ai pas proposée dans ma réponse, car il est inutile de se lancer dans l'utilisation de calculs mutiprécision pour déterminer si un nombre est premier avec l'algorithme "naïf" dont il est question ici, le temps de calcul augmentant rapidement avec le nombre considéré.

Déjà, pour un nombre représenté sur 64 bits, ce n'est pas évident, mais acceptable:

En gros, sur 64 bits, on peut aller jusqu'a n=2.E19. Comme on teste les valeurs jusqu'à RacineCarrée(n), soit 2^32, dans le pire des cas, on aura une boucle qui fera 4 294 967 296 tours, ce qui est encore admissible, mais si, à l'aide d'un bibliothèque multiprécision, on passe sur 128 bits, alors il y aura jusqu'à 2^64 tours, soit 2.E19 tours, et là, ce n'est plus vraiment jouable.
30/01/2007, 21h03
Phils46

merci beaucoup, à présent tout fonctionne et en effet 64 bits c'est deja pas mal ;)

a bientot j'espère