Sito Arystotlesa

Algorytm znajduje wszystkie liczby pierwsze z zakresu od 2 do danej liczby Maxnumber pomniejszonej o 1.
Najpierw tworzy się tablicę od 0 do Maxnuber. Wszystkie pozycje w tablicy oznacza się 'P' - liczba pierwsza. Następnie oblicza się pierwiastek kwadratowy z Maxnumber i oznacza go jako sqrtMAX. Potem zaczynając od n = 2 do sqrtMAX szuka sie wielokrotności n w tablicy. Jeżeli znajdzie się je oznacza się ja przez 'N' - nie są to liczby pierwsze. Wszstkie pozycje oznaczone przez 'R' zawierają liczby pierwsze.

Kod w PHP:

<?php
	if(isset($Maxnumber)){
		$ok = true;
		if(strlen($Maxnumber)>5) 
		{
				print("<br><br><b>iczba zbyt duża!</b><BR>");
				$ok = false;
		}
		else {
			for($i = 0; $i<strlen($Maxnumber);  $i++)
			{
				if(!($Maxnumber[$i]>='0' && $Maxnumber[$i]<='9')) { 
						print "<br><br><b>Nieprawidłowa liczba! (nie jest cyfrą)</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>Oto wszystkie liczby pierwsze od 0 do $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();
?>

powrót do strony głównej