Crible d'eratosthene

Commenter

Contenu du snippet

Un petit programme de recherche des nombres premiers en utilisant la méthode d'Eratosthene.
Algorithme différent de celui posté la semaine dernière.
Celui de la semaine dernière cherchait les nombres premiers d'une façon classique : le nombre n'est pas premier s'il existe au moins un seul le precedant telle que le modulo est <> de zero.
Par contre pour celui là, pour chaque nombre (non eliminé donc premier), il faut éliminer tous ses multiples (d'où le tableau utilisé).

Source / Exemple : 


/**


     
  •  @author chabacha

 *


     
  • /


class Eratosthene {
	/*Recherche des nombres tels qu'ils ne sont divisibles
	que par eux même (ou 1!)*/
	public static void main (String args[]) {
	    int i,j,borne_sup=1100,nbr_int_premier=0;
	    boolean []tableau_premiers = new boolean [borne_sup-1];
	    
	    for (i=0;i<=tableau_premiers.length-1;i++) 
	    {
	        tableau_premiers[i]=true;
	    }
	    // le chiffre 2 est premier "par defaut", d'ailleurs, tous au debut.
	    for (i=2;i<=borne_sup;i++) 
	    {
	    	if (tableau_premiers[i-2]==true){ // bypass les nbres non 1ers
		        j=i+1;
		        while (j<=borne_sup) 
	 	        {
			        if ((j%i)==0) tableau_premiers[j-2]=false;
			        j++;
		        }
		        nbr_int_premier++;
		   	    if (nbr_int_premier%13!=0) System.out.print(i+" ");
		   	    	else System.out.println(i+" ");
	    	}
	    }
		/*for (i=0;i<=tableau_premiers.length-1;i++) 
		{
		    if (tableau_premiers[i]==true)
		    {
		 	    nbr_int_premier++;
		   	    if (nbr_int_premier%13!=0) System.out.print(i+2+" ");
		   	    	else System.out.println(i+2+" ");
		    }
		}*/
	    System.out.println("");
	    System.out.println("Nomre de nbr premiers : "+nbr_int_premier+" entre "+2+" et "+borne_sup);
	}
}

Conclusion :


Devinez quel est le traitement le plus long ?
voilà la prochaine foi je posterai une animation (SWT, lib GC) d'un tableau de cent cases.

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.