#!/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+1; 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!!!
	$r=2;
	while ((($i+1)*$r)<($n+1)) {
#		print "$r   ($i+1)    $array[($i+1)*$r-1]\n";
		$array[($i+1)*$r-1]=0;
	 	$r++;}	

#		print "$k :  $array[$k] -- $i : $array[$i] \$test:$test \n ";
						
# print "\n\n"; 

	}
###########################End of sieve##############
#Print result: ################################
print "\n\n\n tested up to $n \n\t\t"; #print what was done
foreach (@array) { 
	$count++;
	if ($count % 20 ==0) {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";