Chotkos's Blog

Programowanie i informatyka

Sito Erastotenesa

Dzisiaj omówię bardzo cwany algorytm dot. liczb pierwszych – Sito Erastotenesa. Pozwala on szybko wygenerować tablicę liczb pierwszych w przejrzysty i zrozumiały sposób:

Nasz program polegać będzie na tym iż jeżeli spotka liczbę „nieoznaczoną” to uzna ją za liczbę pierwszą i oznaczy wszystkie jej wielokrotności., jeżeli spotka oznaczoną, to po prostu przejdzie dalej. Może zaprezentuję to na n=10.

kolor czerwony – oznaczona , kolor niebieski – nieoznaczona, kolor zielony uznana za pierwszą.

PS – zawsze zaczynamy od dwójki, bo jedynka zaznaczyłaby nam wszystkie liczby do n 😉

1.

2 3 4 5 6 7 8 9 10 //pusta tablica

2

2 3 4 5 6 7 8 9 10 // wybranie dwójki jako nieoznaczonej

3

2 3 4 5 6 7 8 9 10 //oznaczanie wielokrotności

4

2 3 4 5 6 7 8 9 10 // wybranie trójki jako nieoznaczonej

5

2 3 4 5 6 7 8 9 10  //wykreślamy wielokrotności trójki

(…)

10

2 3 4 5 6 7 8 9 10 //LP z tego ciągu to 2,3,5,7


Wydaje mi się że już wiecie o co chodzi, więc teraz opublikuję kod:

Dla C++ Dla Pascala

Zadanie do wykonania


Reklamy

Luty 3, 2010 - Posted by | Algorytmy, Programowanie | ,

Brak komentarzy.

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s

%d blogerów lubi to: