Liczby pierwsze

Prezentacja Grzegorza Lewczuka

LICZBY PIERWSZE

Liczba pierwsza, to liczba naturalna która posiada dokładnie 2 dzielniki: jeden i sama siebie. Czyli: 2,3,5,7,11,13,17,19, itd…

Główne własnoœci liczb pierwszych:

-Najmniejszy różny od jedynki dzielnik naturalny liczby naturalnej, większej od jednoœci, jest liczba pierwsza.

–Euklides pokazał, że żaden skończony zbiór nie zawiera wszystkich liczb pierwszych:

-Niech X będzie skończonym zbiorem liczb pierwszych. Niech x będzie iloczynem wszystkich liczb występujacych w X (gdy X jest puste, to x=1). Jedynym wspólnym dzielnikiem liczb x oraz x+1 jest 1. Zatem żadna liczba pierwsza, występujaca w X, nie jest dzielnikiem liczby x+1. Ale x+1 > 1. Więc x+1 ma dzielnik p, który jest liczba pierwsza. Liczba pierwsza p nie należy do X (bo jest dzielnikiem liczby x+1).

-Każda liczba naturalna większa od 1 daje się jednoznacznie zapisać w postaci iloczynu skończonego niemalejacego ciagu pewnych liczb pierwszych. Twierdzenie to był w stanie udowodnić już Euklides (stworzył niezbędne narzędzia), ale uczynił to dopiero Gauss. Twierdzenie to oznacza, że liczby pierwsze sa w pewnym sensie atomami, z których przy pomocy mnożenia zbudowane sa pozostałe liczby.

Wyznaczanie liczb pierwszych

Do wyznaczania liczb pierwszych z danego przedziału, najczęœciej używany jest algorytm sito Eratostenesa, który polega na wykreœlaniu ze zbioru liczbowego wszystkich wielokrotnoœci wczeœniejszych liczb.

Opis: Wprowadzamy n, okreœlajaca nam przedział liczbowy z jakiego będziemy wyznaczali liczby pierwsze. Tworzymy tablicę n-elementowa(t[n]), w której każdy element ma przypisana wartoœć 0. Tworzymy pętlę która sprawdzi liczby od 2 do pierwiastka z n(for(int i=2; i*i<=n;i++)). W œrodku tej pętli tworzymy kolejna pętlę, która ‘wykreœla’ wielokrotnoœci liczby i ze zbioru, zmieniajac ich wartoœć na 1(t[i]=1). Wszystkie liczby z tablicy z wartoœcia 0, sa pierwszymi.

Kod:

#include <iostream>

using namespace std;

int n;

int main()

{

cin>>n;

int t[n+1];

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

{

if (t[i] == 1)

continue; // jeżeli dana liczb  jest wykreœlona

for (int j = 2 * i ; j <= n; j += i) //{// przejdŸ od liczby 2 * i do n przesuwajac się o i

t[j] = 1;

}

cout << „Liczby pierwsze z przedziału od 0 do ” << n << „:” << endl; //wypisywanie liczb

for (int i = 2; i <= n; i++) {

if (t[i] != 1)

cout << i << endl;

}

return 0;

}

Innym algorytmem jest sito liniowe, polegajace na wykorzystaniu twierdzenia:

Liczba złożona x może zostać jednoznacznie zapisana jako:

x = p^k × q

Zasada działania algorytmu sita liniowego jest następujaca: Za p i q przyjmujemy pierwsza liczbę zbioru. Za k przyjmujemy 1. Następnie w pętli generujemy liczby x = p^k × q dla kolejnych k = 1,2,… do momentu, gdy x przekroczy n. Wygenerowane liczby x usuwamy ze zbioru. Wtedy za q przyjmujemy następna liczbę w zbiorze i całoœć powtarzamy. Jeœli pierwsze x, dla k = 1 wykracza poza n, to zmieniamy p i q na następna liczbę, która ze zbioru S nie została jeszcze wyrzucona. Algorytm kończymy, jeœli iloczyn p × q wykracza poza n. Z przedstawionej tablicy wynika jasno, iż każde x pojawia się tylko jeden raz, nie dochodzi więc do zbędnych przebiegów. Kod:

#include <iostream>

using namespace std;

int main()

{

int i,n,p,q,x;

cin >> n;

int S[n+1];

for(i = 2; i <= n; i++) S[i] = 1;

p = 2;

while(p * p <= n)

{

q = p;

while(p * q <= n)

{

x = p * q;

while(x <= n)

{

S[x] = 0;

x *= p;

}

while(!S[++q]);

}

while(!S[++p]);

}

for(i = 2; i <= n; i++) if(S[i]==1) cout << i << ” „;

cout << endl;

system(„pause”);

return 0;

}

Także ja sam przygotowałem swój algorytm wyszukujacy liczby pierwsze. Sprawdza on czy dana liczba jest podzielna przez jakakolwiek liczbę pierwsza mniejsza od niej samej.

Polega on na tym że tablica tp, przechowuje nam kolejne liczby pierwsze, które znajdujemy. Na poczatku przechowuje jedynie liczbę 2. Następnie w pętli sprawdza, czy dana liczba jest podzielna przez jakakolwiek liczbę z tablicy tp, jeœli tak to przechodzi dalej, jeœli nie to dopisuje ta liczbę jako kolejny element tablicy tp. Kod:

#include <iostream>

using namespace std;

int n, tp[1000000], a=2, czyp;

int main()

{

tp[0]=1;

tp[1]=2;

cin >> n;

for(int i=3; i< n;i++)

{

for(int j=1;j<a;j++)

{

if(i%tp[j]==0)

{

czyp=1;

}

}

if (czyp==0)

{

tp[a]=i;

a++;

}

czyp=0;

}

for(int i = 0; i < a; i++) cout << tp[i] << ” „;

cout << endl;

system(„pause”);

return 0;

}

Postanowiłem sprawdzić szybkoœć działania tych trzech algorytmów, dla wyszukania liczb pierwszych z różnych zakresów, oto wyniki:

Dla n=1000:

Sito Eratostenesa: 16ms

Sito liniowe: 16ms

Mój algorytm: 16ms

Wyniki identyczne, czyli algorytmy radza sobie równie dobrze dla niewielkich liczb.

Dla n=10000:

Sito Eratostenesa: 110ms

Sito liniowe: 78ms

Mój algorytm: 265ms

Tutaj już widać jak mój algorytm odstaje wydajnoœcia od reszty, czego oczywiœcie można było się spodziewać, po niskim stopniu skomplikowania.

Dla n=100000

Sito Eratostenesa: 766-781ms

Sito liniowe: 656-672ms

Mój algorytm: ~14000ms

Jak widać algorytm, który sam opracowałem już mocno odstaje od reszty. Przy dużych liczbach lepiej używać algorytmów sprawdzonych. Jedyne co mnie zaciekawiło, to to że Sito liniowe jest nieco bardziej wydajne od sita Eratostenesa, a mimo to jest mniej znane i rzadziej używane.

Praca ta to wynik moich badań, na temat liczb pierwszych, które przeprowadzałem w ramach projektu „Regionalny program stypendialny dla uczniów szczególnie uzdolnionych”

Grzegorz Lewczuk