Sujet Précédent Sujet Suivant

Crible d'erastophène

Fermé
benjamim Messages postés 1629 Date d'inscription samedi 29 mars 2008 Statut Membre Dernière intervention 1 février 2017 - 4 avril 2014 à 21:42
benjamim Messages postés 1629 Date d'inscription samedi 29 mars 2008 Statut Membre Dernière intervention 1 février 2017 - 4 avril 2014 à 23:45
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

Réponse 1 / 4
KX Messages postés 16733 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 janvier 2024 3 015
4 avril 2014 à 23:11
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
Réponse 2 / 4
benjamim Messages postés 1629 Date d'inscription samedi 29 mars 2008 Statut Membre Dernière intervention 1 février 2017 83
Modifié par benjamim le 4/04/2014 à 23:16
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
Réponse 3 / 4
KX Messages postés 16733 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 janvier 2024 3 015
4 avril 2014 à 23:34
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
Réponse 4 / 4
benjamim Messages postés 1629 Date d'inscription samedi 29 mars 2008 Statut Membre Dernière intervention 1 février 2017 83
4 avril 2014 à 23:45
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