Opole, dn. 10 marca 2004

Laboratorium Algorytmów i Struktur Danych

Temat:

Analiza algorytmu wyszukiwania liczb pierwszych
metodą „Sita Eratostenesa”

Autor: Dawid Najgiebauer

Informatyka, sem. II, grupa lab. 11

Prowadzący: dr inż. Jan Sadecki

1. Temat

Przeanalizować i zbadać algorytm wyszukiwania liczb pierwszych metodą „Sita Eratostenesa”.

2. Analiza, projektowanie

Celem badania jest sprawdzenie praktycznego zastosowania i efektywności algorytmu wyszukującego wszystkie liczby pierwsze w zadanym zakresie przy użyciu metody zwanej „sitem Eratostenesa”.

Każda z liczb naturalnych zostanie zaprezentowana, jako indeks w tablicy, której komórki mogą przyjmować jedną z dwóch wartości: 1 - liczba jest liczbą pierwszą; 0 - liczba nie jest liczbą pierwszą. Założeniem startowym jest, że każda z liczb począwszy od 1, jest liczbą pierwszą (a wiec tablica wypełniona jest jedynkami). Algorytm będzie „wykreślał” liczby, które pierwszymi nie są, a więc wstawiał w tablicę na odpowiadające liczbą pozycje wstawiał wartość 0.

1. „Sito Eratostenesa”

Metoda ta bazuje na bardzo prostym założeniu i spostrzeżeniu. Podejście do liczby pierwszej w tej metodzie jest odwrotne od definicji liczby pierwszej. Tak więc, zamiast sprawdzać podzielność kolejnych liczb naturalnych przez znalezione liczby pierwsze, zaproponował wyrzucanie ze zbioru liczb naturalnych wielokrotności kolejnych liczb. To, co zostanie, będzie zbiorem liczb pierwszych, które nie posiadają innych podzielników jak 1 i same siebie. Jest to najszybsza metoda wyszukiwania liczb pierwszych w ograniczonym zbiorze.

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

Tabela 1. 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

21

22

23

24

25

26

27

1

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

1

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

1

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

1

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

Liczby/Opis

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.

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

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

Następną wolną liczbą jest 5. Postępujemy zatem identycznie jak wcześniej. Zauważamy, że pierwszą z wykreślonych liczb jest 25.

Można zauważyć, że przy kolejnych liczbach nie będą już wykreślane żadne ich wielokrotności. Zatem otrzymaliśmy tablicę z liczbami pierwszymi.

Pozostaje naturalne pytanie, do jakiej liczby pierwszej należy dojść, aby mieć pewność, iż reszta zbioru składa się wyłącznie z liczb pierwszych. Na powyższym przykładzie widać, że pierwszą skreślaną przy badaniu wielokrotności liczby 2 była liczba 4, dla 3 była to liczba 9, zaś dla 5 - 25. Tak więc łatwo można zauważyć, że pierwszą skreślaną liczbą był jej kwadrat. Tak więc odpowiedź brzmi - do liczby pierwszej nie większej od części całkowitej z pierwiastka z ostatniej liczby w zbiorze wyjściowym. W powyższym przykładzie była ta liczba 27.
zatem jedyną liczbą pierwszą nie większą od tego pierwiastka jest liczba 5.

Z rozważań tych wynikają dwa istotne wnioski, które można wykorzystać do optymalizacji algorytmu:

1. Wyrzucanie liczb prowadzimy aż do momentu, gdy kwadrat badanej liczby będzie większy od największej liczby w zbiorze.

2. Zawsze pierwszą z wyrzucanych liczb jest kwadrat analizowanej liczby.

Poniżej przedstawiono schemat algorytmu:

3. Implementacje i wykonanie badania algorytmu

1. Założenia

Badanie zostaną wykonane dla ciągów o różnej długości. Począwszy od ciągu o długości 50 000 elementów a na ciągu zawierającym 1 milion elementów skończywszy, zwiększając za każdym razem długość ciągu o 50 000. Chcąc uzyskać wyniki uśrednione czasu działania każdego z algorytmów, zostanie zmierzony czas łączny dla 100. Ponieważ algorytm niszczy pierwotną tablicę, przed przystąpieniem do badania zostanie utworzonych także 100 identycznych tablic, które kolejno będą „podawane” algorytmowi. Ma to na celu zminimalizowanie wpływu czasu alokacji i dealokacji pamięci na badanie czasu wykonywania się algorytmu. Następnie zmierzony czas zostanie podzielony przez liczbę wykonań.

2. Implementacja algorytmu wyszukiwania liczb pierwszych metodą „sita Eratostenesa”

void Sito(char *tab, long n)

{

long i,j;

tab[1]=0;

for(i=2;i*i<=n;i++)

if (tab[i])

{

j=i*i;

tab[j]=0;

for(j+=i;j<=n;j+=i)

if (tab[j]!=0) /* Ten warunek to optymalizacja ze względu na bardzo długi czas potrzebny do zapisu wartości w tablicy dynamicznej o wysokim adresie. Nie jest on uwzględniony w schemacie na stronie 4. */

tab[j]=0;

}

}

4. Wyniki badania

Czas wykonywania algorytmu dla poszczególnych danych przedstawiono na wykresie poniżej.

Rysunek 1. Wykres zależności czasu wykonywania algorytmu od wielkości przeszukiwanej tablicy (=maksymalnej liczby pierwszej, jaka będzie mogła być wyłoniona).

5. Uwagi i wnioski z testowania i uruchamiania

1. Czas wyszukiwania licz pierwszych opisywanym algorytmem jest wprost proporcjonalny do ilości analizowanych liczb (=wartości liczby, względem której wyszukiwane liczby pierwsze mają być mniejsze lub równe).

2. Charakterystyka zależności czasu wykonywania od długości tablicy tworzy trend liniowy.

3. Odstępstwo 6 początkowych punktów od wyznaczonej linii trendu jest związane z adresowaniem wysokich adresów. Jest to wykonywane przez kompilator. Jak widać adresowanie do wielkości ok. 300k jest wyraźnie szybsze niż powyżej tej granicy.

Wyjątek stanowi tu element 0 tablicy, który jest zupełnie niewykorzystywany a wprowadzony został wyłącznie celem ułatwienia indeksowania. Ma on przypisaną wartość „zero”.

6 Dawid Najgiebauer

Implementacje i wykonanie badania algorytmu 5

Temat 3

STOP

tab[J]=0

T

N

J≤N

J=J+I

J=I*I

tab[J]=0

N

I++

T

tab[I]=0

N

T

I*I≤N

I=2

tab[1]=0

tab[], N

Schemat 1. Schemat algorytmu wyszukiwania liczb pierwszych metodą „sita Eratostenesa”

---