Publicité
+ Répondre à la discussion
Affichage des résultats 1 à 3 sur 3
  1. #1
    Invité régulier
    Inscrit en
    mai 2005
    Messages
    44
    Détails du profil
    Informations forums :
    Inscription : mai 2005
    Messages : 44
    Points : 7
    Points
    7

    Par défaut Crible de Sundaram

    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.

  2. #2
    Membre Expert
    Homme Profil pro
    Inscrit en
    mars 2011
    Messages
    542
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : mars 2011
    Messages : 542
    Points : 1 162
    Points
    1 162

    Par défaut

    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é.
    La perfection est atteinte, non pas lorsqu’il n’y a plus rien à ajouter, mais lorsqu’il n’y a plus rien à retirer. - Antoine de Saint-Exupéry

  3. #3
    Invité régulier
    Inscrit en
    mai 2005
    Messages
    44
    Détails du profil
    Informations forums :
    Inscription : mai 2005
    Messages : 44
    Points : 7
    Points
    7

    Par défaut

    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

+ Répondre à la discussion
Cette discussion est résolue.

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •