Aristotle's sieve



Aristotle's sieve

The algorithm finds all prime numbers from 2 to given Maxnumber-1.
First you need to create an array of nubers starting from 0 to Maxnuber. All positions in array you mark as 'P' - prime. Next you find a square root of Maxnumber denoted by sqrtMAX. Then starting with n = 2 to sqrtMAX you look for each multiple of n in the array. If you find them you put 'N' - not prime in that positions in array. All positions with 'P' indicate prime numbers.

Enter a number (<99999):



PHP code: 
<?php
	if(isset($Maxnumber)){
		$ok = true;
		if(strlen($Maxnumber)>5) 
		{
				print("<br><br><b>Number too big!</b><BR>");
				$ok = false;
		}
		else {
			for($i = 0; $i<strlen($Maxnumber);  $i++)
			{
				if(!($Maxnumber[$i]>='0' && $Maxnumber[$i]<='9')) { 
						print "<br><br><b>Incorrect number! (NOT DIGIT)</b><BR>";
						$ok = false;
						break;
				}
			}
		}
		if($ok) {
			$sqrtMAX = sqrt($Maxnumber);
			$a[0] = 'N'; 
			$a[1] = 'N';
			for($i=2; $i<$Maxnumber; $i++)
				$a[$i]='P';
			for($i = 2; $i <=$sqrtMAX; ++$i)
                    for($factor = 2; $factor*$i<$Maxnumber; ++$factor)
                               $a[$factor*$i] = 'N';
			$Maxnumber--;
			print "<br><b>Here are all prime nubers from 0 to $Maxnumber:</b><br>";
			$Maxnumber++;			
			$j=0;
			for($i=2; $i<$Maxnumber; $i++) {
				if($a[$i]=='P') 
				{
					print "$i ";
					$j++;
					if(!($j % 10)) print "<br>";
				}
			}
		}
	}
	f();
?>

Back to main page