#! /usr/bin/perl -w

# calcul de nombre premier par le crible d'eratosthene
# jve - décembre 2006

use strict;

# passage de la valeur max en paramètre
my $max = $ARGV[0];

# creation de la liste des entiers allant de 2 a max
print "creation de la liste de 2 a $max\n";
my @listecomplete;
for (my $i=2;$i<=$max;$i++){$listecomplete[$i-2]=$i;}

# et on rentre dans le vif du sujet
print "application de l'algorithme d'eratosthene\n";

# valeur de test
my $quit=0;

# on parcours toutes les valeurs de listecomplete
foreach my $i (@listecomplete){

	# a moins que le test de sortie soit vrai, on exécute le code suivant
	unless ($quit==1){

		# une valeur barrée est mise à -1, ces valeurs sont exclus
		# donc on ne rentre que si la valeur est un entier positif non exclus
	        if($i != -1){

			# pour chaque entier, on le compare a tous les autres entiers...
			foreach my $j (@listecomplete){
				# ...qui ne sont pas exclus
				if ($j != -1){

					# a moins que les deux entiers soient égo, on test le modulo
					# si le résultat est 0, alors j est un multiple de i, donc on exclus j
					# en mettant sa valeur dans le tableau a -1
					unless ($i == $j){ if ($j % $i == 0){$listecomplete[$j-2]=-1;}}
				}
			}
			# on regarde quelle est la prochaine valeur entière qui suis i			
			my $suivant=$i;
			while($listecomplete[$suivant-2] == -1){
				$suivant++;
			}
			
			# si le carré de la prochaine valeur entière est supérieur au max de la liste d'entier, 
			# alors on peut arrêter de chercher : tous les nombres non barrés sont premiers
			if((my $carre = $listecomplete[$suivant-2] ** 2) > $max){
					$quit=1;
					print "$listecomplete[$suivant-2]^2 = $carre est supérieur à $max\n";
					print "les nombres restants dans l'intervalle sont premiers\n";
			}
		}
	}
}

# un peu d'affichage et stockage dans un fichier local
#
print "affichage des nombres premiers trouvés\n";
foreach my $i (@listecomplete){
	unless ($i == -1){print "$i ";}
}
open(LST,">nb_premier.txt");
foreach my $nb (@listecomplete){
	unless ($nb == -1){ print LST "$nb \n";}
}
close LST;
print "\n\n";