Bonjour,
Je vous propose un nouvel élément à utiliser : Nombres Premiers
Donne les nombres premiers compris entre deux nombres quelconques
Qu'en pensez-vous ?
Bonjour,
Je vous propose un nouvel élément à utiliser : Nombres Premiers
Donne les nombres premiers compris entre deux nombres quelconques
Qu'en pensez-vous ?
Mei,
La fonction déterminant si un nombre est premier mérite des améliorations.
Elle fait trop de tours et de tests.
Hello,
Il y à des tours de boucles inutiles de 0 à "a" ici.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8 for(int c=0;(c<=b)&&(a<=b);c++) { if (c==0) cout<<"\t La liste des nombres premiers de "<<a<<" a "<<b<<endl<<endl; if ((c<a)||(prim(c)==false)) continue; cout<<"\t "<<c<<endl; }
La condition est redondante ici, b commence à 2, a!=b suffit (si a==2 on à a==b).
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10 bool prim(int a) { bool p=true; for(int b=2;(a!=b)&&(a!=2);b++) if((a<2)||(a%b==0)) { p=false; break; } return p; }
Le a<2 devrait être testé avant la boucle aussi, ou dans la boucle avec une condition typeOn utilise la racine carré ici car si on prend 100 par exemple :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10 bool prim(int a) { bool p = true; // il n'y à pas de diviseurs supérieur à la racine carrée de a (enfin, ils auront déjà été testés) for(int b=2, stop=sqrt(a); b<=stop; ++b) if(a%b == 0) { p=false; break; } return p; }
a == 100
sqrt(100) == 10
bien qu'on ai 100 = 50*2, et donc 50 > 10, cela sera déjà testé par 100 % 2.
Après il y à pas mal d'autres optimisations possibles, par exemple itérer que sur les nombres impairs dans la boucle principale, ce qui divise le nombre d'appel de la fonction prim par 2.
Il y à probablement un paquet d'autres optimisations possibles, mais je ne connait pas assez le sujet.![]()
Hia,
Oui, mais si tu écris ta boucle comme tu l'as fait, la racine carrée sera calculée à chaque tour de boucle, il faut donc la reporter avant l'entrée dans la boucle.
C'est une manière d'écrire cette boucle de calcul qu'on retrouve presque systématiquement.
D'autre part, il faut commencer par éliminer le cas <= 2.
Puis la boucle sur b commencera à 3, avec un pas de 2, jusqu'à la racine.
Et voilà l'essentiel des optimisations qu'on peut faire, sans avoir à creuser les algorithmes.![]()
merci pour vos reponses je suis debutant voila pourquoi
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
39
40
41 #include <stdio.h> #include <stdlib.h> #include <math.h> /* Générateur de nombres Premiers */ /* Inférieurs ou égaux à 4294967295 */ /* Auteur : Lemariey Jean-Philippe */ int main(int argc, char *argv[]) { div_t resultat; int i = 3; int j = 1; int n = 0; int r = 0; double m = 0.0; printf ("Ceci est un générateur de nombres Premiers inférieurs ou égaux à N \n"); printf("Votre valeur de N svp : "); scanf("%i", &n); printf("\n 2 "); while (i <= n) { j = 2; resultat = div(i, j); r = resultat.rem; m = sqrt((double)i); // pas la peine de chercher au delà de // racinecarrée i while (j <= m && r != 0) { j++; resultat = div(i, j); r = resultat.rem; } if (j > m) { printf("%d ", i); } i += 2; //On ne teste que les nombres impairs } return 0; }
Partager