liczby pierwsze!! Opcje

[Buby]

nie wiem jak napisac taki skrypt ktory pokazywalby liczby pierwsze z przedzialu od 0 do n! (IMG:http://forum.php.pl/style_emoticons/default/sad.gif) Prosze o pomoc!!

[talee]

Bierzemy sobie kolejno kandydatów i próbujemy dzielić przez liczby pierwsze, które trzymamy w tablicy. Jeżeli się podzieli to ne jest pierwsza w przeciwnym wypadku est. Dzielimy tylko przez te liczby pierwsze spełniające warunek pierwsza * 2 <= kandydat.

[php:1:455022dbeb]<?php

// funkcja wypisuje wszystkie liczby
// pierwsze z zakresu od [1..$zakres]

function pierwsze($zakres) {

if ($zakres >= 2) {
echo '1 -> 2', "n";
$tab_pierwsze[] = '2'; // eliminujemy przypadek trywialny
}

$tab_pierwsze_count = 1;

$j = 2;

for ($i = 3; $i <= $zakres; $i++) {

$pierwsza = true;
$sqrt = floor(sqrt($i)) + 1;

for ($k = 0; $k < $tab_pierwsze_count; $k++) {
if ($i % $tab_pierwsze[$k] == 0) {
$pierwsza = false; // nie jest pierwsza
break;
}
if ($tab_pierwsze[$k] > $sqrt) {
break; // nie dzielimy przez p, takie że 2 * p > i
}
}

if ($pierwsza) {
$tab_pierwsze[] = $i;
++$tab_pierwsze_count;
echo "$j -> $in";
++$j;
}
}
}
?>[/php:1:455022dbeb]