package fr.ensicaen.se.lecture6.crible;

import java.util.*;

/**
 * Cette classe génère les nombres premiers jusqu'à un maximum
 * spécifié par l'utilisateur. L'algorithme utilise le crible d'Ératosthène
 * <p>
 * Ératosthène de Cyrène, b. c. 276 BC, Cyrène, Libye --
 * d. c. 194, Alexandrie. Le premier homme à calculer la
 * circonférence de la Terre.<p>
 * L'algorithme est plutôt simple. Étant donné un tableau d'entiers
 * commençant à 2. Éliminer tous les multiples de 2. Chercher le
 * prochain entier non éliminé, et éliminer tous ses multiples.
 * Répéter jusqu'à la racine carré du maximum.
 *
 * @author Alphonse
 * @version 13 Fev 2012
 */
public class Eratosthene
{

    public static void main( String[] args ) {
        int[] nombres = Eratosthene.genereNombresPremiers(100);
        for (int i = 0; i < nombres.length; i++) {
            System.out.print(nombres[i] + ", ");
        }
        System.out.println("");
    }

    /**
     * @param valeurMax le nombre limite de la génération.
     */
    public static int[] genereNombresPremiers( int valMax )
    {
	if (valMax >= 2)  // le seul cas valide
	{
	    // déclarations
	    int s = valMax + 1; // taille du tableau
	    boolean[] f = new boolean[s];
	    int i;
	    // initialise le tableau à vrai.
	    for (i = 0; i < s; i++)
			f[i] = true;
	    f[0] = f[1] = false;  	// se débarrasser des nombres premiers connus

		// crible
	    int j;
	    for (i = 2; i < Math.sqrt(s) + 1; i++)
	    {
			if (f[i] != false) // si i n'est pas éliminé, éliminer ses multiples.
		    	for (j = 2 * i; j < s; j += i)
					f[j] = false; // les multiples ne sont pas premiers
	    }

	    // combien de premiers sont faits ?
	    int compteur = 0;
	    for (i = 0; i < s; i++)
			if (f[i] != false)
		    	compteur++; // ajoute au compteur
	    int[] premiers = new int[compteur];

	    // mettre les nombres premiers dans le tableau des résultats
	    for (i = 0, j = 0; i < s; i++)
		if (f[i] == true) // si premier
		    premiers[j++] = i;
	    return premiers; // retourne les nombres premiers
	}
	else // valeurMax < 2
	    return new int[0]; // retourne un tableau nul si l'entrée est mauvaise.
    }
}