Discussion :

[Rhadamante]

Bonjour,

Je vous propose un nouvel élément à utiliser : Nombres Premiers

Donne les nombres premiers compris entre deux nombres quelconques

Qu'en pensez-vous ?

[droggo]

Mei,

La fonction déterminant si un nombre est premier mérite des améliorations.

Elle fait trop de tours et de tests.

[Iradrille]

Hello,

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

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

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

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

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.

[droggo]

Hia,

Code :

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

   for(int b=2, stop=sqrt(a); b<=stop; ++b)

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.

[Rhadamante]

merci pour vos reponses je suis debutant voila pourquoi

[hastur34]

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