/**
 * @file cribleEratosthene.cpp
 * TD n°6 :  sem06-td-Cpp2
 * @author l'équipe pédagogique 
 * @version 1 26/01/06
 * @brief Test du crible d'Eratosthène
 * Structures de données et algorithmes - DUT1 Paris 5
 */
 
#include <iostream>
#include <cmath>
using namespace std;
 
#include "Liste.h"

/**
 * @brief Liste des nombres premiers par l'algorithme du crible d'Eratosthène
 * @param[in] n : borne de la plage ]1, n] de recherche des nombres premiers
 * @param[in,out] l : la liste des nombres premiers sur ]1, n] 
 */
void cribleEratosthene(unsigned int n, Liste& l) {	
	initialiser(l);				// Créer le crible (une liste de vide)
	for (int i=n; i>=2; --i)	// Liste des nombres de 2 à n
		inserer(l, 0, i);
	unsigned int indCandidat = 0;
	unsigned int candidatNbPrem = lire(l, indCandidat);
	unsigned int borne = (unsigned int) sqrt(n); // Borne les passes du crible

	unsigned int i; // indice de balayage de la liste
	while (candidatNbPrem <= borne) {
		i = indCandidat + 1;
		/* suppression des multiples du nombre premier candidat */
		while (i<longueur(l)) {
			if ((lire(l, i) % candidatNbPrem) == 0)
				supprimer(l, i);
			else 
				++i;
		}
		indCandidat++;
		candidatNbPrem = lire(l, indCandidat);
	}
}
				
/* Recherche des nombres premiers par la méthode du crible d'Eratosthène */ 
int main(int argc, char* argv[]) {
	
	int n; // Recherche des nombre premiers inférieurs ou égal à n
	std::cout << "Recherche des nombres premiers dans l'intervalle ]2..n]\n";
	cout << "Entrez n : ";
	cin >> n;
	
	Liste crible;
	cribleEratosthene(n, crible);
				
	cout << "Liste des " << longueur(crible) 
	     <<" nombres premiers dans l'intervalle ]2.." << n << "] : " << endl;
	for (unsigned int i = 0; i < longueur(crible); ++i) 
		cout << (lire(crible, i)) << " ";
	cout << endl;
	
	detruire(crible); // désallocation du crible
	
	return 0; 
}