Crible de Sundaram [Résolu]

[ganon551]

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 :

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
 
#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;
}

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.

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.

[pyros]

Salut,

Je ne connaissait pas ce crible mais d'après http://villemin.gerard.free.fr/Wwwgv...r/sundaram.htm:
"Si N est dans ce tableau, Alors 2N + 1 n'est pas premier"
et
"Si N n'est pas dans ce tableau, Alors 2N + 1 est premier."

Donc l.39, tu devrais avoir logiquement prime[modif*2 + 1] = false;.
Mais tu devrais utiliser 2 tableau. Un tableau "list" qui dit si un nombre est dans le tableau ou pas, et un tableau "prime" qui dit s'il est premier ou pas, car à la l.39 tu écrase une valeur que tu n'as pas encore traité.

[ganon551]

Merci pour ta réponse.

Je me suis rendu compte de mon erreur, celle où j'écrase la valeur que je viens d'attribuer, juste après avoir posté ici, comme quoi

Par contre j'avais été sur le site que tu me proposes mais il est différent de tout ce que j'ai vu, il n'indique pas les mêmes choses, et pour programmer ce genre de tableau ça va augmenter la complexité de l'algorithme.

En toute logique et selon wiki, et d'autres sites, une fois qu'on a fait les deux boucles i et j, on devrait avoir le bon NOMBRE de premier - 1 (puisque 2 n'est pas compté). En effet, on est sensé appliquer (selon mes sources) 2n + 1 à tout n restant, et dire que le résultat est premier. Du coup pour tout n restant il existe un premier dans l'intervalle, donc le nombre de n restant devrait indiquer le nombre de premiers.

Du coup j'ai résolu mon problème en écrivant ce message
Au final la boucle modif ne sert à rien, je n'ai qu'a modifier mon code pour qu'il affiche les premiers, et en ajoutant un test à la dernière boucle, ça marche, on a donc ça :

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
 
#include <iostream>
#include <math.h>
#include <vector>
#include <cstdlib>
 
#define MAX 10000
 
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;
		}
	}
 
	int compteur = 0;
 
	for(int indice = 1; indice < MAX; indice++)
	{
	    if(prime[indice] && (2*indice+1) < MAX)
	    {
	        compteur++;
	    }
	}
 
	cout << compteur << endl;
 
 
return 0;
}

ça nous donne bien le nombre de premier - 1.

Merci encre pour ta réponse