Nombres Premiers

Présentation
Donne les nombres premiers compris entre deux nombres quelconques
Téléchargement
Compatibilité
Windows
0  0 
Téléchargé 49 fois Voir les 5 commentaires
Détails
Avatar de Rene Malraud
Membre du Club
Voir tous les téléchargements de l'auteur
Licence : Autre
Date de mise en ligne : 23 janvier 2017




Avatar de droggo droggo - Expert confirmé https://www.developpez.com
le 10/07/2013 à 20:10
Mei,

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

Elle fait trop de tours et de tests.
Avatar de Iradrille Iradrille - Expert confirmé https://www.developpez.com
le 10/07/2013 à 21:09
Hello,

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; 
        }
Il y à des tours de boucles inutiles de 0 à "a" ici.

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; 
}
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
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.
Avatar de droggo droggo - Expert confirmé https://www.developpez.com
le 11/07/2013 à 12:56
Hia,
Citation Envoyé par Iradrille  Voir le message
Code : Sélectionner tout
   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.
Avatar de Rhadamante Rhadamante - Membre du Club https://www.developpez.com
le 13/07/2013 à 12:09
merci pour vos reponses je suis debutant voila pourquoi
Avatar de hastur34 hastur34 - Futur Membre du Club https://www.developpez.com
le 19/08/2015 à 12:53
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.
Contacter le responsable de la rubrique C