Crible d'erastophène

benjamim Messages postés 1642 Date d'inscription   Statut Membre Dernière intervention   -  
benjamim Messages postés 1642 Date d'inscription   Statut Membre Dernière intervention   -
Bonjour,
j'essai de faire le crible d'erasophène mais rien n'y fait. Je bloque.
J'ai tenté de 2 manières (voir la partie mise en commentaire) mais ça ne marche pas. Si vous pouviez me dire là où est mon erreur.

Merci :) 

package Exo4p8;
import java.util.Scanner;
public class exo4p8 {
	
	public static void main(String[] args) {
	
		// TODO Auto-generated method stub
		
		
		
	int n, i, j, N;

	Scanner sc = new Scanner(System.in);
	System.out.print("Tapez l'entier");   	
	N = sc.nextInt();
	
	int[] Tab = new int [N];
	
	for (i=0;i<N;i++)
	{
Tab[i]=i+1;	
	}
	
	Tab[0]=0;
	i=1;
	
	while(Tab[i]<=N)
	{
		for(j=2; j<Tab[i]; j++)
		{
			if(Tab[i]%j==0)
			{
				Tab[i]=0;
			}
			Tab[i]=Tab[i+1];
		}
	}
	
	/*
	for(i=2;i<N;i++)
	{
		if(Tab[i]%2 == 0)
		{
		Tab[i] = 0;
		}
	}
	
	
	for(j=3;j<N;j++)
	{
		for(i=3;i<N;i++)
		{
		
			if(Tab[j] != 0)
			{
				if(Tab[i]%j == 0)
				{
				Tab[i] = 0;
				}
				
			}
		}	
	}


	*/
	for(i=0;i<N;i++)
	{
		if(Tab[i] != 0)
		{
			System.out.print(Tab[i]+"est premier.");   
		}
	}
	
}
}

4 réponses

  1.
    KX Messages postés 19031 Statut Modérateur 3 020
     
    Bonsoir,

    Dans tes deux codes tu as 
    if(Tab[i]%j==0)
    or cela ne correspond pas du tout au crible d'Ératosthène qui cherche les multiples, pas les diviseurs !

    Tu devrais regarder cet article, pour comprendre comment fonctionne l'algorithme avant de commencer à le coder :

    http://fr.wikipedia.org/wiki/Crible_d'Ératosthène
    0
  2. benjamim Messages postés 1642 Date d'inscription   Statut Membre Dernière intervention   84
     
    Justement, je m'inspire de cet article depuis le début mais je ne parviens pas à saisir l'idée.. :/

    Pour moi, le 2éme code devrait marcher mais il m'affiche 2/3/5/7/9/11/...etc

    Benjamim
    0
  3. KX Messages postés 19031 Statut Modérateur 3 020
     
    La crible d'Ératosthène se base sur un principe d'élimination, ce qui correspond aux nombres barrés sur l'image animée.

    Dans ton code où apparaissent les nombres que tu as explorés ou non ?

    De plus je m'interroge quant au type de ton tableau, le but étant d'indiquer si un nombre est premier, il n'y a que deux possibilités : vrai ou faux. Alors pourquoi avoir utilisé un tableau d'entiers, là où clairement on devrait avoir des booléens ?

    Voici un bon début et une bonne fin pour ton code, je te laisse voir le milieu... 

    int n = sc.nextInt();

boolean[] prime = new boolean[n];
boolean[] explore = new boolean[n];

// ...

for (int i=0; i<n; i++)
    if (prime[i])
        System.out.println(i+" est premier");
    0
  4. benjamim Messages postés 1642 Date d'inscription   Statut Membre Dernière intervention   84
     
    En fait, j'avais une consigne où je devais faire un tableau d'entier ^^
    Les nombres explorés non premiers deviennent 0, les autres restent tel qu'elle.

    C'est pour ça que je bloque ahah (mais c'est le même principe, le faux correspond à mon zéro).
    0