Login lub e-mail Hasło   

Liczby pierwsze - sito Eratostenesa

Odnośnik do oryginalnej publikacji: http://www.i-lo.tarnow.pl/edu/inf/alg/pr(...)ex.html
Już w czasach starożytnych znano metodę opisaną przez greckiego uczonego Eratostenesa z Cyreny. Podszedł on do rozwiązania od drugiej strony.
Wyświetlenia: 19.979 Zamieszczono 03/11/2006

Eratostenes (Eratostenes z Cyreny) urodził się w 276 roku p.n.e, zmarł w 194 p.n.e. Był greckim uczonym, filozofem matematykiem, , astronomem, geografem oraz poetą. Jego osiągnięcia to oszacowanie średnicy Ziemi raz odległości od Słońca i Księżyca, pomiar kąta nachylenia ekliptyki do równika niebieskiego, propozycja wprowadzenia roku przestępnego, metoda znajdowania liczb pierwszych nazwana na jego cześć sitem Eratostenesa. Kierował biblioteką w Aleksandrii.

W poprzednim rozdziale opisaliśmy znajdowanie liczb pierwszych na podstawie ich definicji, tj. sprawdzając podzielność przez liczby mniejsze. Sposób ten nie jest najefektywniejszą metodą wyszukiwania liczb pierwszych - musimy wykonywać określoną ilość czasochłonnych dzieleń, tym większą, im większą wartość ma badana liczba.

W czasach starożytnych znano lepszą metodę opisaną przez greckiego uczonego Eratostenesa z Cyreny. Podszedł on do rozwiązania od drugiej strony - zamiast sprawdzać podzielność kolejnych liczb naturalnych przez znalezione liczby pierwsze, zaproponował wyrzucanie ze zbioru liczb naturalnych wielokrotności kolejnych liczb, które nie zostały wcześniej wyrzucone. To, co zostanie, będzie zbiorem liczb pierwszych, które nie posiadają innych podzielników jak 1 i same siebie. Metoda ta została nazwana sitem Eratostenesa i jest najszybszą metodą wyszukiwania liczb pierwszych w ograniczonym zbiorze.

Zobaczmy jak działa sito Eratostenesa. Spróbujmy wg tej metody odszukać wszystkie liczby pierwsze w zbiorze 20 początkowych liczb naturalnych.

Generacja liczb pierwszych przy pomocy sita Eratostenesa

{ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 }

Oto początkowy zbiór liczb. Najpierw usuniemy z niego liczbę 1 - nie jest to liczba pierwsza, ponieważ nie posiada dokładnie dwóch różnych podzielników.

{ 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 }

Bierzemy pierwszą liczbę 2 i usuwamy ze zbioru wszystkie jej wielokrotności. W ten sposób pozbyliśmy się liczb parzystych. Zauważ iż obliczanie wielokrotności nie wymaga mnożenia - wystarczy dodawać daną liczbę.

{ 2 3 5 7 9 11 13 15 17 19 }

Następną wolną liczbą jest 3. Usuwamy ze zbioru wszystkie wielokrotności liczby 3. Pozostaną więc liczby niepodzielne przez 2 i przez 3.

{ 2 3 5 7 11 13 17 19 }

Wykonane - w zbiorze pozostały same liczby pierwsze.

 

Przed opisem algorytmu musimy zdecydować, w jaki sposób będziemy reprezentować w pamięci komputera zbiór liczb. Najprostszym rozwiązaniem wydaje się być tablica wartości logicznych. Liczbę określa indeks elementu tablicy. Wartość elementu określa z kolei, czy dana liczba jest w zbiorze czy też jej tam nie ma. Na przykład:

t[5] - element ten odnosi się do liczby 5.

t[5] = true - liczba 5 jest w zbiorze.

t[5] = false - liczba 5 została ze zbioru wyrzucona.

Na początku wpiszemy do każdego elementu wartość true - wszystkie liczby będą w zbiorze. Następnie w elementach, których indeks jest równy wartości wyrzucanych liczb, umieścimy false. Na koniec przeglądniemy całą tablicę i wypiszemy te indeksy, dla których wskazywane elementy zawierają wciąż wartość true.

Dane wejściowe

g - górny kres przedziału, w którym poszukujemy liczb pierwszych, g N

Dane wyjściowe

Kolejne liczby pierwsze zawarte w przedziale od 2 do g.

Zmienne pomocnicze

i - służy do sterowania pętlami iteracyjnymi, i N
t[ ] - tablica logiczna odwzorowująca zbiór liczbowy. Indeksy elementów przebiegają wartości od 2 do g
w - służy do tworzenia kolejnych wielokrotności, w N

krok 1: Czytaj g
krok 2: Dla i = 2,3,...,g wykonuj t[i] true
krok 3: Dla i = 2,3,...,g wykonuj kroki 4...7
krok 4:     w 2i
krok 5:     Dopóki w g wykonuj kroki 6,7. Inaczej wykonaj następny obieg pętli z kroku 3.
krok 6:         t[w] false
krok 7:         w w + i 
krok 8: Dla i = 2,3,...,g  jeżeli  t[i] = true,  to pisz i
krok 9: Zakończ algorytm

Prezentowany algorytm Sita Eratostenesa jest maksymalnie uproszczony. Na początku odczytujemy górny kres przedziału, w którym będziemy wyznaczać liczby pierwsze umieszczając go w zmiennej g.

Następnie wykonywane są kolejno trzy pętle iteracyjne:

Pętla nr 1: - inicjalizacja
ustawia wszystkie elementy tablicy t[ ] na true. Zwróć uwagę, iż tablica jest ustawiana od elementu o indeksie 2. Zgodnie z tym, co powiedzieliśmy wyżej, tablica t[ ] odzwierciedla zbiór liczb naturalnych, w którym wartościami kolejnych liczb są indeksy elementów, natomiast zawartość tych elementów określa, czy reprezentowane przez nie liczby są (true) lub nie są (false) obecne w zbiorze.

Pętla nr 2: - eliminacja
usuwa ze zbioru wszystkie wielokrotności kolejnych liczb. Dokonujemy tego bez żadnych sprawdzeń, co oczywiście nie jest zbytnio efektywne, ale za to bardzo proste. W zmiennej w tworzymy pierwszą wielokrotność i-tej liczby. Następnie wszystkie elementy o indeksach równych kolejnym wielokrotnościom ustawiamy na false. Po zakończeniu pętli 2 w tablicy t[ ] wartość true pozostaje jedynie w elementach, których indeksy są liczbami pierwszymi.

Pętla nr 3: - prezentacja
przegląda kolejne elementy tablicy t[ ] i jeśli mają one wartość true, wyświetla ich indeks. Po wykonaniu tej pętli w oknie konsoli otrzymamy wszystkie liczby pierwsze zawarte w przedziale od 2 do g.


Wydruk z uruchomionego programu
Wyszukiwanie liczb pierwszych sitem Eratostenesa
------------------------------------------------
(C)2005 mgr Jerzy Wałaszek I LO w Tarnowie

Podaj granicę = 500

2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
73 79 83 89 97 101 103 107 109 113
127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199 211 223 227 229
233 239 241 251 257 263 269 271 277 281
283 293 307 311 313 317 331 337 347 349
353 359 367 373 379 383 389 397 401 409
419 421 431 433 439 443 449 457 461 463
467 479 487 491 499

Koniec, naciśnij klawisz ENTER...
Microsoft Visual Basic 2005 Express Edition

 

Borland
Delphi 7.0
Personal
Edition
//     Sito Eratostenesa
//============================
// (C)2004 mgr Jerzy Wałaszek
// I LO w Tarnowie
//----------------------------

program Erato;

{$APPTYPE CONSOLE}

const
MAX_LP = 10000000; // maksymalna długość zbioru

var
t : array[2..MAX_LP] of boolean;
i,w,g : cardinal;

begin
writeln('Wyszukiwanie liczb pierwszych sitem Eratostenesa');
writeln('------------------------------------------------');
writeln('(C)2004 mgr Jerzy Walaszek I LO w Tarnowie');
writeln;
write('Podaj granice = '); readln(g); writeln;
if g > MAX_LP then
writeln('Granica zbyt wielka')
else
begin

for i := 2 to g do t[i] := true;
for i := 2 to g do
begin

w := i + i;
while w <= g do
begin

t[w] := false;
w := w + i;
end;
end;
for i := 2 to g do
if
t[i] then write(i : 8);
writeln;
end;
writeln;
writeln('Koniec, nacisnij klawisz ENTER...');
readln;
end.
Borland
C++ Builder
6.0
Personal
Edition
//     Sito Eratostenesa
//============================
// (C)2004 mgr Jerzy Wałaszek
// I LO w Tarnowie
//----------------------------

#include <iostream>
#include <iomanip>

using namespace std;

main()
{
const unsigned MAX_LP = 1000000; // maksymalna długość zbioru
bool t[MAX_LP + 1];
unsigned i,w,g;
char s[1];

cout << "Wyszukiwanie liczb pierwszych sitem Eratostenesa\n"
"------------------------------------------------\n"
"(C)2004 mgr Jerzy Walaszek I LO w Tarnowie\n\n"
"Podaj granice = "
;
cin >> g; cout << endl;
if(g > MAX_LP)
cout << "Granica zbyt wielka\n";
else
{
for(i = 2; i <= g; i++) t[i] = true;
for(i = 2; i <= g; i++)
{
w = i + i;
while(w <= g)
{
t[w] = false; w += i;
}
}
for(i = 2; i <= g; i++)
if(t[i]) cout << setw(8) << i;
cout << endl;
}
cout << "\n\nKlawisz Enter = KONIEC";
cin.getline(s,1);
cin.getline(s,1);
}
Microsoft
Visual
Basic 2005
Express
Edition
'     Sito Eratostenesa
'============================
' (C)2005 mgr Jerzy Wałaszek
' I LO w Tarnowie
'----------------------------

Option Explicit On

Module
Module1

Sub main()
Const MAX_LP = 10000000 ' maksymalna długość zbioru

Dim t(MAX_LP) As Byte
Dim
i, w, g As UInteger

Console.WriteLine("Wyszukiwanie liczb pierwszych sitem Eratostenesa")
Console.WriteLine("------------------------------------------------")
Console.WriteLine("(C)2005 mgr Jerzy Wałaszek I LO w Tarnowie")
Console.WriteLine()
Console.Write("Podaj granicę = ")
g = Val(Console.ReadLine)
Console.WriteLine()
If g > MAX_LP Then
Console.WriteLine("Granica zbyt wielka")
Else
For
i = 2 To g : t(i) = 1 : Next
For
i = 2 To g
w = i + i
While w <= g
t(w) = 0
w += i
End While
Next
For
i = 2 To g
If t(i) > 0 Then Console.Write("{0,8}", i)
Next
Console.WriteLine()
End If
Console.WriteLine()
Console.WriteLine("Koniec, naciśnij klawisz ENTER...")
Console.ReadLine()
End Sub

End Module
Python
# -*- coding: cp1250 -*-
# Sito Eratostenesa
#============================
# (C)2005 mgr Jerzy Wałaszek
# I LO w Tarnowie
#----------------------------

print "Wyszukiwanie liczb pierwszych sitem Eratostenesa"
print "------------------------------------------------"
print "(C)2005 mgr Jerzy Walaszek I LO w Tarnowie"
print
g = int(raw_input("Podaj granice = "))
print
t = range(g + 1)
for i in range(2, g + 1):
w = i + i
while w <= g:
t[w] = 0
w += i
for i in range(2, g + 1):
if t[i]: print "%7d" % i,
print
print
raw_input
("Koniec, nacisnij klawisz ENTER...")
JavaScript
<html>
<head>
</head>
<body>
<div align=
"center">
<form name=
"frmerato"
style="border: 1px outset #FF9933;
padding-left: 4px; padding-right: 4px;
padding-top: 1px; padding-bottom: 1px;
background-color: #FFCC66"
>
<h3 style=
"text-align: center">
Sito Eratostenesa
</h3>
<p style=
"text-align: center">
(C)2004 mgr Jerzy Wałaszek - I LO w Tarnowie
</p>
<hr>
<p style=
"text-align: center">
Podaj górną granicę zbioru
</p>
<p style=
"text-align: center">
<input type=
"text" name="T1" size="20" value="100">
</p>
<p style=
"text-align: center">
<input type=
"button" value="Szukaj" name="B1" onclick="main()">
</p>
<p id=
"data_out" style="text-align: center">...</p>
</form>

<script language=javascript>

// Sito Eratostenesa
//============================
// (C)2004 mgr Jerzy Wałaszek
// I LO w Tarnowie
//----------------------------

function main()
{
var t = new Array();
var i,w,g,s;

g = parseInt(document.frmerato.T1.value);
if(isNaN(g))
s = "<font color=Red><b>ZŁE DANE</b></font>";
else
{
for(i = 2; i <= g; i++) t[i] = true;
for(i = 2; i <= g; i++)
{
w = i + i;
while(w <= g)
{
t[w] = false; w += i;
}
}
s = "";
for(i = 2; i <= g; i++) if(t[i]) s += i + " ";
}
document.getElementById("data_out").innerHTML = s;
}
</script>
</div>
</body>
</html>
 
   

Poniższe, przykładowe programy są praktyczną realizacją omawianego w tym rozdziale algorytmu. Zapewne można je napisać bardziej efektywnie. To już twoje zadanie. Dokładny opis stosowanych środowisk programowania znajdziesz we wstępie. Programy przed opublikowaniem w serwisie edukacyjnym zostały dokładnie przetestowane. Jeśli jednak znajdziesz jakąś usterkę (co zawsze może się zdarzyć), to prześlij o niej informację do autora. Pozwoli to ulepszyć nasze artykuły. Będziemy Ci za to wdzięczni.

 

 

W algorytmie wyszukiwania liczb pierwszych metodą Sita Eratostenesa nie występuje nigdzie potrzeba dzielenia. Wyznaczając wielokrotności wykonujemy jedynie proste dodawanie, które komputer realizuje bardzo szybko. Z tego powodu prezentowany algorytm czasowo jest najszybszym algorytmem rozwiązującym zadanie wyszukiwania liczb pierwszych.

Dla celów badawczych przyjmijmy za operację dominującą wyrzucanie ze zbioru wielokrotności kolejnych liczb. Operacja taka składa się z wyznaczenia wartości tej wielokrotności oraz wstawienia do elementu tablicy (o indeksie równym wielokrotności) wartości logicznej false. W tym celu program należy wyposażyć w odpowiedni licznik. Wykonanie tego zadania, z uwagi na jego prostotę, pozostawiam ambitnym czytelnikom. W poniższej tablicy zebraliśmy rezultaty pracy takiego programu.

Wyniki badania ilości wykonanych operacji wyrzucania liczb
Zakres poszukiwania
liczb pierwszych
Ilość
operacji wyrzucania
Wzrost
2...10 8 -
2...100 283 35,375
2...1000 5070 17,915
2...10000 73669 14,530
2...100000 966751 13,123
2...1000000 11970035 12,382
2...10000000 142725365 11,924
2...100000000 1657511569 11,613

W pierwszej kolumnie mamy przeszukiwany przez algorytm zakres liczb naturalnych. Zakres przyrasta 10 razy.

Druga kolumna zawiera ilość operacji wyrzucania liczby ze zbioru, którą wykonał algorytm Sita Eratostenesa.

W trzeciej kolumnie liczymy wzrost operacji wyrzucania przy rozszerzeniu zakresu poszukiwań. Wzrost ten jest liczony jako iloraz liczby operacji z bieżącego wiersza przez liczbę operacji z wiersza poprzedniego.

Na podstawie danych zebranych w tej tabelce postaraj się odpowiedzieć na następujące pytania:

  1. Do jakiej liczby zmierza wzrost ilości operacji wyrzucania przy 10 krotnym wzroście zakresu poszukiwań liczb pierwszych?
  2. Jaką klasę czasowej złożoności obliczeniowej posiada ten algorytm?
  3. Uzasadnij swój wybór klasy złożoności obliczeniowej na podstawie analizy działania algorytmu.
  4. Dlaczego przyrost stabilizuje się dopiero dla dużych zakresów?
  5. Jaki wniosek można wysunąć na temat statystycznego rozkładu częstości występowania liczb pierwszych?

 

 
 Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.
 

Podobne artykuły


61
komentarze: 41 | wyświetlenia: 9423
22
komentarze: 8 | wyświetlenia: 2114
13
komentarze: 8 | wyświetlenia: 2031
13
komentarze: 55 | wyświetlenia: 21874
58
komentarze: 20 | wyświetlenia: 80680
31
komentarze: 8 | wyświetlenia: 56536
27
komentarze: 10 | wyświetlenia: 20337
23
komentarze: 5 | wyświetlenia: 19525
14
komentarze: 8 | wyświetlenia: 100809
11
komentarze: 2 | wyświetlenia: 5274
9
komentarze: 3 | wyświetlenia: 15203
8
komentarze: 41 | wyświetlenia: 3831
12
komentarze: 3 | wyświetlenia: 29778
49
komentarze: 18 | wyświetlenia: 64971
37
komentarze: 9 | wyświetlenia: 28513
 
Autor
Artykuł




Brak wiadomości


Dodaj swoją opinię
W trosce o jakość komentarzy wymagamy od użytkowników, aby zalogowali się przed dodaniem komentarza. Jeżeli nie posiadasz jeszcze swojego konta, zarejestruj się. To tylko chwila, a uzyskasz dostęp do dodatkowych możliwości!
 

© 2005-2018 grupa EIOBA. Wrocław, Polska