Raport z projektu

Przedmiot: Algorytmy i złożoność

PROJEKT:LICZBY PIERWSZE

Autor: Kamil Adamuszek

1. Zadanie

Porównaj złożoność i czasy dwóch algorytmów wyznaczania liczb pierwszych.

2. Metoda naiwna(prosta)

Metoda ta polega na sprawdzaniu podzielności przykładowej liczby a przez liczby od 2

do a-1. Jeśli żadna z tych liczb nie jest podzielnikiem a to liczba a jest liczbą pierwszą.
Algorytm tej metody wygląda następująco:

for (liczba=2;liczba<(granica+1);liczba++)
{
for (dzielnik=2;dzielnik<(liczba+1);dzielnik++)
{
if (liczba%dzielnik==0)
{
if (liczba!=dzielnik)

{

dzielnik=liczba+1;

}

else

{

printf(fp,"%d",liczba);
}
}
}
}

Algorytm ten jest prosty i efektywny w przypadku ,gdy chcemy zbadać pierwszość

niewielkiego zakresu liczb. Jednak do badania dużego przedziału nie powinno się go jednak
używać, ponieważ ten algorytm znajdowania liczb pierwszych ma złożoność obliczeniową
rzędu O(n

2

) lub O(√n) po optymalizacji polegającej na sprawdzaniu podzielności liczby a

przez liczby od 2 do √a

3. Metoda zwana sitem Eratostenesa

Algorytm ten jest nazywany sitem, ponieważ „odsiewa” wszystkie liczby złożone z

podanego przedziału. Eratostenes zauważył, że liczby złożone są wielokrotnościami kolejnych
liczb pierwszych (np. 4, 6, 8,... - są wielokrotnościami 2; natomiast 6, 9, 12,... są
wielokrotnościami 3 itd.). Wystarczy więc z danego przedziału pozbyć się wszystkich
wielokrotności 2, z liczb, które zostaną wykreślić kolejno wszystkie wielokrotności 3, potem
wielokrotności 5 (bo 4 zostało już wykreślone) itd. "Odsiewając" w ten sposób liczby złożone,
pozostawiamy same liczby pierwsze.

Realizację sita Eratostenesa ilustruje poniższy fragment programu, który wypisuje

liczby pierwsze używając tablicy boolowskiej.

tab = new bool[zakres + 1];
for(liczba = 2; liczba <= zakres; liczba++)
tab[liczba] = true;
do = (unsigned int)sqrt(zakres);

for(liczba = 2; liczba <= dok; liczba++)

if(tab[liczba])
{
d = liczba * liczba;
while(d <= zakres)
{
tab[d] = false; d += liczba;
}
}
for(liczba = 2; liczba <= zakres; liczba++) if(tab[liczba])
{
cout<<liczba<<"\n";
}
cout << endl;

delete [] tab;

Jest to metoda o wiele szybsza o metody naiwnej(prostej). Jej złożoność czasowa jest

rzędu O(n log log n).

4. Testy

Próba została wykonana około 300 razy dla obydwóch metod obliczeniowych. Czas

natomiast został zmierzony w milisekundach.

Ilość liczb

Czas wykonania algorytmu w przypadku

metody naiwnej

Czas wykonania w

przypadku metody zwanej

sitem Eratostenesa

0

0

0

10000

76

16

20000

282

28

30000

586

38

40000

996

48

50000

1504

58

60000

2123

67

70000

2830

81

80000

3646

90

90000

4551

99

100000

5511

108

5. Porównanie zależności między czasem działania algorytmu a zakresem

0

1000

2000

3000

4000

5000

6000

0

10000 20000 30000 40000 50000 60000 70000 80000 90000 100000

Cz

as

w ms

Zakres

Porównanie metody naiwnej z metodą zwaną

sitem Erastotenesa

Czas

Czas 2

6. Wnioski

Metoda naiwna jest akceptowalna dla niewielkiego zakresu liczb jest to

według mnie zakres 2-2000 dla większego zakresu metoda to jest mało wydajna gdyż
jest czas wykonania gwałtownie wzrasta. Metoda zwana sitem Eratostenesa jest
efektywna dla każdego zakresu, ponieważ czas jej wykonania nie wzrasta gwałtownie
jak w przypadku metody naiwnej lecz logarytmicznie. Złożoność czasowa sita
Eratostenesa wynosi O(n log log n).