algorytm.org

Sito Eratostenesa

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Sito Eratostenesa
Ocena użytkowników:***** / 44
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 26 lipca 2005 19:36

Około roku 200 p.n.e grecki matematyk Eratostenes podał algorytm na znajdowanie liczb pierwszych. Nazwa pochodzi od sposobu w jaki są one znajdowane. Wszystkie liczby po kolei przesiewa się - usuwane są spośród nich wszystkie wielokrotności danej liczby.
Przykład:


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

23456789101112131415161718192021222324252627282930

Teraz bierzemy pierwszą liczbę z tabeli (2) i począwszy od następnej wykreślamy z niej wszystkie te liczby, które są przez nią podzielne.

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

Bierzemy kolejną liczbę (3) i począwszy od następnej wykreślamy z tabeli podzielne przez nią.

23 5 7   11 13   17 19   23 25   29 

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

23 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.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiAda
.ada
.ada
***** / 4
Tomasz LubińskiC#MS Visual Studio .net
.cs
.cs
***** / 6
Tomasz LubińskiC/C++
.cpp
.cpp
***** / 24
MarianC/C++C++ streams
.cpp
.cpp
***** / 6
Kamil DębowskiC/C++C++
.cpp
.cpp
***** / 6
Tomasz LubińskiDelphi/Pascal
.pas
.pas
***** / 6
Tomasz LubińskiJavaz pobieraniem danych od użytkownika
.java
.java
***** / 6
gchlebusJavagotowa do użycia klasa implementująca metodę sita eratostenesa
.java
.java
***** / 11
Jakub KoniecznyJava_Block
.jbf
.jbf
***** / 1
Kamil SochaPython
.py
.py
***** / 9
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 28 października 2012 15:21
Dodaj komentarz