Bonjour à tous,
J'essaie désespérément de comprendre ce crible, j'ai bien compris la théorie (cf http://en.wikipedia.org/wiki/Sieve_of_Sundaram), mais dès que je veux l'implémenter ça ne marche pas du tout.
Pour info, j'ai cherché sur google, tout ce que je trouvais en anglais et en français, j'ai dû trouver une dizaine de sources, mais elles étaient toutes fausses. Ou alors j'ai mal compris le but de cet algo.
Du coup, voici mon code :
Assez simple, on supprime les valeurs dans le tableau pour i + j + 2 * i * j, puis on cherche les valeurs restantes à true, et normalement (selon toutes les sources que j'ai trouvées), le nombre pour (valeur_restante) * 2 + 1 est premier.
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 #include <iostream> #include <omp.h> #include <math.h> #include <vector> #include <cmath> #include <cstdlib> #define MAX 100 using namespace std; int main() { vector<bool> prime(MAX,1); int limiteDiv = MAX / 2; for (int i = 1; i < limiteDiv; i++) { for (int j = 1; j <= i; j++) { int n = i + j + 2 * i * j; if (n >= MAX) { break; } prime[n] = false; } } prime[2] = true; for(int modif = 1; modif < limiteDiv; modif++) { if(prime[modif] == true) { prime[modif] = false; prime[modif*2 + 1] = true; cout << "modif = " << modif << " et modif*2+1 = " << modif*2 + 1 << endl; } } int compteur = 0; for(int indice = 1; indice < MAX; indice++) { if(prime[indice] == true) { compteur++; } } cout << compteur << endl; return 0; }
Ce qui se vérifie à peu près. Si vous remarquez, j'ai ajouté une petite ligne pour afficher la valeur de la variable modif et la valeur sensée être un premier (donc modif * 2 + 1). Si vous l'exécutez vous remarquerez que le programme sort bien tous les nombres premiers, mais que pour certaines valeurs de modif étant premier, il nous sort des multiples de 3 et de 5, n'étant forcément pas premières.
Si quelqu'un peut m'expliquer où je fais fausse route, et pourquoi toutes les sources du net semblent être fausses, ça m'éclairerait beaucoup.
Merci.
Partager