liczby pierwsze Opcje

[Jabol]

temat wydzielony od: http://forum.php.pl/viewtopic.php?t=9078
Chodzi o sprawdzanie licz czy są pierwsze.

Najprosciej (choc nie najwydajniej) sprawdzic podzielnosc liczby X przez wszystkie liczby calkowite od 2 do sqrt(X) (sqrt - pierwiastek kwadratowy). Jesli się przez ktorakolwiek z nich dzieli to nie jest to liczba pierwsza (wyjatkiem jest liczba 2, ktora jest liczba pierwsza).

Najprościej jest podzielić przez wszystkie liczy pierwsze mniejsze od sqrt(X) i większe od 2.

[Cudi]

Niom, niestety masz racje. Przepisałem algorytm z podanej strony na php:
[php:1:cf773fee3d]<?php
$intX = 10000; // ilosc liczb do przecedzenia przez sito
$arrPrimes = range( 1, $intX );

for( $i = 2; $i <= $intX; $i++ )
{
$z = 2;

while( $i * $z <= $intX )
{
unset( $arrPrimes[ array_search( ( $i * $z ), $arrPrimes ) ] );
$z++;
}
}
?>[/php:1:cf773fee3d]
I niestety dla 10000 liczb pierwszych czas wynosi ok. 20 sekund (IMG:http://forum.php.pl/style_emoticons/default/sad.gif) Ale jeśli chcemy wypisac tylko określoną ilość liczb pierwszych to taki czas jest chyba zadowalający (IMG:http://forum.php.pl/style_emoticons/default/winksmiley.jpg)