Implémentation du crible d'Erathostène

**pingu** · 12/03/2009, 16h40

Bonjour,
J'écris un programme de recherche de nombres premiers basé sur le principe du crible d'Erathostène.
Mon code tourne sans problème pour une recherche dans un intervalle allant de 2 à 89, mais dès que j'entre une recherche de nombres premiers pour un intervalle supérieur (à partir de [2 ; 90] donc), j'ai une erreur "terminate called after throwing an instance of 'std::bad_alloc' ".
Mon code :

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
 
#include <iostream>
#include <iomanip>
#include <math.h>
 
using namespace std;
 
//---------------------------------------------------------------------------
const int MAX = 1000000;
 
struct TListePrem{
  int  nbrMax;
  int* pPrem;
  int  nbrPrem;
};
 
void InitialiserTListePrem(TListePrem &listePrem);
int LireInt(int min, int max);
void Erathostene(TListePrem &listePrem);
void AfficherPremiers(const TListePrem &listePrem);
int Stop();
void DetruireTListePrem(TListePrem &listePrem);
 
////---------------------------------------------------------------------------
////Fonction main
////---------------------------------------------------------------------------
int main(int argc, char* argv[])
{
  TListePrem listePrem;
  InitialiserTListePrem(listePrem);
  do {
    cout << endl << "Votre naturel maximum ? ";
    listePrem.nbrMax = LireInt(0,MAX);
    Erathostene(listePrem);
    AfficherPremiers(listePrem);
  } while (!Stop());
  DetruireTListePrem(listePrem);
  return 0;
}
////---------------------------------------------------------------------------
////Fin de la fonction main
////---------------------------------------------------------------------------
 
 
/* InitialiserTListePrem
 * Initialise les éléments de la struct
 * Tous les éléments ont pour valeur initiale 0 ou NULL (suivant le type)
 */
void InitialiserTListePrem(TListePrem &listePrem) {
	listePrem.nbrMax = 0;
	listePrem.nbrPrem = 0;
	listePrem.pPrem = NULL;
}
 
/* Erathostene
 * Calcule les nombres premiers compris entre 2 et la variable entière nbrMax de la structure dont la référence est passée comme paramètre de la fonction
 */
void Erathostene(TListePrem &listePrem) {
	int i,j,c=0,counter=0;
	int max = listePrem.nbrMax;
	int tab[max];
 
	tab[0] = tab[1] = 0;
 
	for(i=2; i<=max; i++)
		tab[i] = i;
	for(i=2; i<sqrt(max); i++) {
		if(tab[i]) {
			for(j = i*i; j<=max; j+=i) {
				tab[j] = 0;
				counter++;
			}
		}
	}
	int *finalTab = new int[max-counter];
 
	for(int a=0; a<=max; a++) {
		if(tab[a] != 0) {
			finalTab[c] = tab[a];
			c++;
		}
	}
	listePrem.nbrPrem = c;
	listePrem.pPrem = finalTab;
}
 
/* LireInt
 * Fonction lisant un entier entré par l'utilisateur, compris entre un minimum et un maximum entrés comme paramètres de la fonction
 */
int LireInt(int min, int max) {
	int n;
	cin >> n;
 
	while(n < min || n > max) {
		cout << "Votre naturel maximum n'est pas compris entre "<<min<<" et "<<max<<endl<<"Veuillez entrer un nouveau naturel maximum : ";
		cin >> n;
	}
 
	return n;
}
 
/* AfficherPremiers
 * Fonction affichant les nombres premiers calculés pour une structure dont la référence est passée comme paramètre de la fonction
 */
void AfficherPremiers(const TListePrem &listePrem) {
	cout << "Liste des "<<listePrem.nbrPrem<<" nombres premiers calculés, de 2 à "<<listePrem.nbrMax<<" :" <<endl;
 
	for(int i=0; i<listePrem.nbrPrem; i++)
			cout<<listePrem.pPrem[i] <<endl;
}
 
/* DetruireTListePrem
 * Fonction détruisant la structure dont la référence est passée comme paramètre de la fonction
 */
void DetruireTListePrem(TListePrem &listePrem) {
	delete listePrem.pPrem;
	listePrem.nbrMax = 0;
	listePrem.nbrPrem = 0;
}

D'après mes petites recherches sur google, ce serait la ligne "int *finalTab = new int[max-counter];" (dans la fonction "Erathostene") qui serait en cause...
Si quelqu'un peut me donner un coup de main pour comprendre l'erreur (et la résoudre

)...

edit : oublié de préciser, je bosse sous Linux (Ubuntu) et compile avec g++.

**Trunks** · 12/03/2009, 16h58

Code :

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

int tab[max];

Ca m'étonne que ça compile

Petite remarque:

Code :

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

InitialiserTListePrem

Au lieu de faire l'initialisation via une fonction externe, pourquoi ne pas le faire via la contructeur de la structure (mauvaise habitude C ?)

Sinon, j'aurait tendance à penser que ton tableau est trop gros et aurais tendance à utiliser la STL plutôt que des tableau de type C.