Téléchargé 1 fois
Vote des utilisateurs
0 
0
Détails
Licence : Non renseignée
Mise en ligne le 23 janvier 2017
Plate-forme :
Windows
Langue : Français
Référencé dans
Navigation
Nombres Premiers
Nombres Premiers
Donne les nombres premiers compris entre deux nombres quelconques
Mei,
La fonction déterminant si un nombre est premier mérite des améliorations.
Elle fait trop de tours et de tests.
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.
La condition est redondante ici, b commence à 2, a!=b suffit (si a==2 on à a==b).
Le a<2 devrait être testé avant la boucle aussi, ou dans la boucle avec une condition type
On utilise la racine carré ici car si on prend 100 par exemple :
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.
| Code : | Sélectionner tout |
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;
} |
| Code : | Sélectionner tout |
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 type
| Code : | Sélectionner tout |
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,
Envoyé par Iradrille
On utilise la racine carré ici car si on prend 100 par exemple :
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.
Envoyé par Iradrille
| Code : | Sélectionner tout |
for(int b=2, stop=sqrt(a); b<=stop; ++b)
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 |
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;
} |
Developpez.com décline toute responsabilité quant à l'utilisation des différents éléments téléchargés.