Implémentation du crible d'Erathostène
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:
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++.
