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!!

[matys]

Masz tutaj algorytm, czly dokladnie rozpisane co trzeba zrobić:

Kod

Przykład:

Odnajdziemy za pomocą sita Eratostenesa wszystkie liczby pierwsze z zakresu od 2 do 30.

Zapisujemy kolejno wszystkie liczby w tabeli.







2|3 |4 |5 |6 |7 |8 |9 |10| 11| 12| 13| 14| 15| 16| 17| 18| 19| 20| 21| 22| 23| 24| 25| 26| 27| 28| 29| 30 |





Teraz bieżemy pierwszą liczbę z tabeli (2) i począwszy od następnej (3) dzielimy przez nią wszystkie kolejne liczby. Te, które są przez nią podzielne wykreślamy z niej.





2 3   5   7   9   11   13   15   17   19   21   23   25   27   29  





Bieżemy kolejną liczbę (3) i dzielimy przez nią pozostałe liczby począwszy od następnej (5, bo 4 już jest wykreślone). Podzielne wykreślamy z tabeli.





2 3   5   7       11   13       17   19       23   25       29  





Kolejną liczbą w tabeli jest 5. Postępujemy jak poprzednio.





2 3   5   7       11   13       17   19       23           29  





W tym momencie możemy zakończyć nasze poszukiwania. Algorytm "mówi", że kolejne wykreślania należy powtarzać, nie dalej jak do liczby będącej zaokrąglonym w dół pierwiastkiem zakresu. U nas jest to: sqrt(30)=5.4772255.., po zaokrągleniu w dół otrzymujemy 5. W tabeli zostały już tylko liczby pierwsze.