Crible d'Eratosthène segmenté
Bonjour à tous,
J'aimerais coder l'algorithme du crible segmenté en c++. J'ai déjà bien exploré le crible normal, et les performances en hausse de la version segmentée m'attirent.
Du coup j'ai écris le code suivant, qui est une version très naïve du crible, je veux juste que ça fonctionne et pouvoir après l'optimiser.
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
|
#include <iostream>
#include <math.h>
#include <vector>
#include <cstdlib>
using namespace std;
int main()
{
int max = 100000;
int square, i, j,k;
int limite = ceil(sqrt(max));
int compteur2 = 0;
int slice;
if(max > 10000)
slice = 10000;
else
slice = limite;
if(limite % 2 != 0)
limite++;
square = ceil(sqrt(limite));
vector<char> tableau(limite, 0x1);
for(i = 2; i < limite; i+=2)
{
tableau[i] = 0x0;
}
for(j = 3; j <= square; j+=2)
{
for(k = j * j; k <= limite; k+= j)
{
tableau[k] = 0x0;
}
}
int compteur = 1;
for(i = 3; i < limite; i+=2)
{
if(tableau[i] == 0x1)
compteur++;
}
std::vector<int> segment(slice,1);
for(int y = limite; y <= max;y+=slice)
{
for(int z = 0; z <= slice; z++)
{
if(z % 2 == 0)
segment[z] = 0;
else
{
if(z+y < max)
segment[z] = z + y;
else
segment[z] = 0;
}
}
for(int g = 3; g <= limite; g+=2)
{
if(tableau[g] == 0x1)
{
for(int h = 1;h <= slice;h++)
{
if(segment[h] != 0)
{
if(segment[h] % g == 0)
segment[h] = 0;
}
}
}
}
for(int r = 1; r <= slice;r++)
{
if(segment[r] != 0)
{
compteur2++;
}
}
}
cout << compteur2+compteur << endl;
return 0;
} |
Bon je sais, le code est sale mais j'ai essayé tellement de choses que forcément ça salit :D
Du coup mon problème est le suivant : Si je déclare max à plus de 100.000, le programme plante au moment de la déclaration du vector<int> segment. Ce que je ne comprend pas, étant donné que je l'initialise avec la variable "slice" qui n'a rien à voir avec "max".
Si je remplace ce vector par un array de int, ça marche très bien.
Autre problème, et c'est peut-être lié, si vous lisez le code vous remarquerez ça :
Code:
1
2
3
4
5
|
if(z+y < max)
segment[z] = z + y;
else
segment[z] = 0; |
C'est la seule solution que j'ai trouvé à un problème, en effet z va de limite à max par pas de slice, à la fin je me retrouve donc avec un vector segment qui fait toujours la même taille (ici 10.000), alors que je n'ai besoin que d'une taille de 10.000 - limite. Je ne sais pas si je me fais bien comprend :aie:
Du coup, est-il possible "proprement" de fixer la taille du vector<int> segment dans ma boucle z ?
Autre question, niveau performance, que vaut-il mieux choisir entre un vector et un array, sachant que je compte déclarer des array/vector de unsigned long long (64 bits donc) d'une taille comprise entre 32k et 256k selon le choix de l'utilisateur ?
Merci pour vos éclaircissements :)
