#!/usr/bin/perl -w
# setting up#############################
#$n=1000; #maximum number to test 
print "This program runs the sieve of Eratosthenes \nEnter number up to which you want to run the sieve: ";
$n=<STDIN>;
if ($n eq "\n") {print "please enter number\n";exit};
chomp ($n);
print "testing up to $n; please wait.\n";

@array=(1..$n); #assign numbers to array

###################start of the sieve###############
#I left some of the bug finding stuff as commented lines 
# -  Note: slot 1 of @array contains 2!

for ($i=1;$i<($n/2)+1; $i++) #loop to pick array entries to use as divisor= $i -
# test only upt $n/2 as divisor - one could choose a better limit here
	{
#	print "divisor tested: $i; testing $array[$i] \n";#reassures the user that the program is doing things :) 

	if ($array[$i]==0){next} #if divisor is already 0 skip to next number in array!!!
	
	for ($k=$i+1;$k<$n;$k++) #loop to pick numerator $k
		{
		if ($array[$k]==0) {next}; # if number is already set at zero skip ahead
		$test = $array[$k] % $array[$i]; #check if divisor in loop fits into numerator
#		print "$k :  $array[$k] -- $i : $array[$i] \$test:$test \n ";

# Rather than looping through the numerator using modulo, one could go through the list of number and just set every $i's number to 0
# would be faster for large divisors
# this might work beautifully with aHash

		if ($test==0) {$array[$k]=0}; #if it fits, then numerator is not prime and set to 0
				
		}				
# print "\n\n"; 

	}
###########################End of sieve##############
#Print result: ################################
print "\n\n\n tested up to $n \n\t"; #print what was done
foreach (@array) { 
	$count++;
	if ($count % 10 ==1) {print "\nNext #$count:\n\t"}; #print a new line every 20 numbers and add a little comment
#############How would this need to be changed to start the lines on 1 ...21....41
	print "\t $_";#print the prime or 0 \t works, because the numbers will not get too big.
}
print "\n";