Discussion :

[Phils46]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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;
}

[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

[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 :

Sélectionner tout - Visualiser dans une fenêtre à part

     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)

[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.
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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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;
}

[la drogue c'est mal]

et avec un double ?

[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

[Emmanuel Delahaye]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[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.

[thewho]

Bonjour,

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.

[Phils46]

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

a bientot j'espère