Prezentacja Grzegorza Lewczuka<\/p>\n
<\/p>\n
LICZBY PIERWSZE<\/strong><\/p>\n Liczba pierwsza<\/strong>, to liczba naturalna kt\u00f3ra posiada dok\u0142adnie 2 dzielniki: jeden i sama siebie. Czyli: 2,3,5,7,11,13,17,19, itd\u2026<\/p>\n G\u0142\u00f3wne w\u0142asno\u009cci liczb pierwszych:<\/p>\n -Najmniejszy r\u00f3\u017cny od jedynki dzielnik naturalny liczby naturalnej, wi\u0119kszej od jedno\u009cci, jest liczba pierwsza.<\/p>\n –Euklides<\/a> pokaza\u0142, \u017ce \u017caden sko\u0144czony zbi\u00f3r nie zawiera wszystkich liczb pierwszych:<\/p>\n -Niech X b\u0119dzie sko\u0144czonym zbiorem liczb pierwszych. Niech x b\u0119dzie iloczynem wszystkich liczb wyst\u0119pujacych w X (gdy X jest puste, to x=1). Jedynym wsp\u00f3lnym dzielnikiem liczb x oraz x+1 jest 1. Zatem \u017cadna liczba pierwsza, wyst\u0119pujaca w X, nie jest dzielnikiem liczby x+1. Ale x+1 > 1. Wi\u0119c x+1 ma dzielnik p, kt\u00f3ry jest liczba pierwsza. Liczba pierwsza p nie nale\u017cy do X (bo jest dzielnikiem liczby x+1).<\/p>\n -Ka\u017cda liczba naturalna wi\u0119ksza od 1 daje si\u0119 jednoznacznie zapisa\u0107 w postaci iloczynu sko\u0144czonego niemalejacego ciagu pewnych liczb pierwszych. Twierdzenie to by\u0142 w stanie udowodni\u0107 ju\u017c Euklides (stworzy\u0142 niezb\u0119dne narz\u0119dzia), ale uczyni\u0142 to dopiero Gauss<\/a>. Twierdzenie to oznacza, \u017ce liczby pierwsze sa w pewnym sensie atomami, z kt\u00f3rych przy pomocy mno\u017cenia zbudowane sa pozosta\u0142e liczby.<\/p>\n Wyznaczanie liczb pierwszych<\/strong><\/p>\n Do wyznaczania liczb pierwszych z danego przedzia\u0142u, najcz\u0119\u009cciej u\u017cywany jest algorytm sito Eratostenesa<\/a>, kt\u00f3ry polega na wykre\u009claniu ze zbioru liczbowego wszystkich wielokrotno\u009cci wcze\u009cniejszych liczb.<\/p>\n Opis: Wprowadzamy n, okre\u009clajaca nam przedzia\u0142 liczbowy z jakiego b\u0119dziemy wyznaczali liczby pierwsze. Tworzymy tablic\u0119 n-elementowa(t[n]), w kt\u00f3rej ka\u017cdy element ma przypisana warto\u009c\u0107 0. Tworzymy p\u0119tl\u0119 kt\u00f3ra sprawdzi liczby od 2 do pierwiastka z n(for(int i=2; i*i<=n;i++)). W \u009crodku tej p\u0119tli tworzymy kolejna p\u0119tl\u0119, kt\u00f3ra \u2018wykre\u009cla\u2019 wielokrotno\u009cci liczby i ze zbioru, zmieniajac ich warto\u009c\u0107 na 1(t[i]=1). Wszystkie liczby z tablicy z warto\u009ccia 0, sa pierwszymi.<\/p>\n Kod:<\/p>\n #include <iostream><\/p>\n using namespace std;<\/p>\n int n;<\/p>\n int main()<\/p>\n {<\/p>\n cin>>n;<\/p>\n int t[n+1];<\/p>\n for (int i = 2; i*i <= n; i++ )<\/p>\n {<\/p>\n if (t[i] == 1)<\/p>\n continue; \/\/ je\u017celi dana liczb\u00a0 jest wykre\u009clona<\/p>\n for (int j = 2 * i ; j <= n; j += i) \/\/{\/\/ przejd\u009f od liczby 2 * i do n przesuwajac si\u0119 o i<\/p>\n t[j] = 1;<\/p>\n }<\/p>\n <\/p>\n cout << „Liczby pierwsze z przedzia\u0142u od 0 do ” << n << „:” << endl; \/\/wypisywanie liczb<\/p>\n for (int i = 2; i <= n; i++) {<\/p>\n if (t[i] != 1)<\/p>\n cout << i << endl;<\/p>\n }<\/p>\n return 0;<\/p>\n }<\/p>\n Innym algorytmem jest sito liniowe, polegajace na wykorzystaniu twierdzenia:<\/p>\n Liczba z\u0142o\u017cona x<\/em> mo\u017ce zosta\u0107 jednoznacznie zapisana jako:<\/p>\n x<\/em> = pk<\/sup><\/em> \u00d7 q<\/em><\/p>\n Zasada dzia\u0142ania algorytmu sita liniowego jest nast\u0119pujaca: Za p<\/em> i q<\/em> przyjmujemy pierwsza liczb\u0119 zbioru. Za k<\/em> przyjmujemy 1. Nast\u0119pnie w p\u0119tli generujemy liczby x<\/em> = pk<\/sup><\/em> \u00d7 q<\/em> dla kolejnych k<\/em> = 1,2,… do momentu, gdy x<\/em> przekroczy n<\/em>. Wygenerowane liczby x<\/em> usuwamy ze zbioru. Wtedy za q<\/em> przyjmujemy nast\u0119pna liczb\u0119 w zbiorze i ca\u0142o\u009c\u0107 powtarzamy. Je\u009cli pierwsze x<\/em>, dla k<\/em> = 1 wykracza poza n<\/em>, to zmieniamy p<\/em> i q<\/em> na nast\u0119pna liczb\u0119, kt\u00f3ra ze zbioru S<\/em><\/strong> nie zosta\u0142a jeszcze wyrzucona. Algorytm ko\u0144czymy, je\u009cli iloczyn p<\/em> \u00d7 q<\/em> wykracza poza n<\/em>. Z przedstawionej tablicy wynika jasno, i\u017c ka\u017cde x<\/em> pojawia si\u0119 tylko jeden raz, nie dochodzi wi\u0119c do zb\u0119dnych przebieg\u00f3w. Kod:<\/p>\n #include <iostream><\/p>\n using namespace std;<\/p>\n int main()<\/p>\n {<\/p>\n int i,n,p,q,x;<\/p>\n cin >> n;<\/p>\n int S[n+1];<\/p>\n for(i = 2; i <= n; i++) S[i] = 1;<\/p>\n p = 2;<\/p>\n while(p * p <= n)<\/p>\n {<\/p>\n q = p;<\/p>\n while(p * q <= n)<\/p>\n {<\/p>\n x = p * q;<\/p>\n while(x <= n)<\/p>\n {<\/p>\n S[x] = 0;<\/p>\n x *= p;<\/p>\n }<\/p>\n while(!S[++q]);<\/p>\n }<\/p>\n while(!S[++p]);<\/p>\n }<\/p>\n for(i = 2; i <= n; i++) if(S[i]==1) cout << i << ” „;<\/p>\n cout << endl;<\/p>\n system(„pause”);<\/p>\n return 0;<\/p>\n }<\/p>\n Tak\u017ce ja sam przygotowa\u0142em sw\u00f3j algorytm wyszukujacy liczby pierwsze. Sprawdza on czy dana liczba jest podzielna przez jakakolwiek liczb\u0119 pierwsza mniejsza od niej samej.<\/p>\n Polega on na tym \u017ce tablica tp, przechowuje nam kolejne liczby pierwsze, kt\u00f3re znajdujemy. Na poczatku przechowuje jedynie liczb\u0119 2. Nast\u0119pnie w p\u0119tli sprawdza, czy dana liczba jest podzielna przez jakakolwiek liczb\u0119 z tablicy tp, je\u009cli tak to przechodzi dalej, je\u009cli nie to dopisuje ta liczb\u0119 jako kolejny element tablicy tp. Kod:<\/p>\n #include <iostream><\/p>\n using namespace std;<\/p>\n int n, tp[1000000], a=2, czyp;<\/p>\n int main()<\/p>\n {<\/p>\n tp[0]=1;<\/p>\n tp[1]=2;<\/p>\n cin >> n;<\/p>\n for(int i=3; i< n;i++)<\/p>\n {<\/p>\n for(int j=1;j<a;j++)<\/p>\n {<\/p>\n if(i%tp[j]==0)<\/p>\n {<\/p>\n czyp=1;<\/p>\n }<\/p>\n }<\/p>\n if (czyp==0)<\/p>\n {<\/p>\n tp[a]=i;<\/p>\n a++;<\/p>\n }<\/p>\n czyp=0;<\/p>\n }<\/p>\n for(int i = 0; i < a; i++) cout << tp[i] << ” „;<\/p>\n cout << endl;<\/p>\n <\/p>\n system(„pause”);<\/p>\n return 0;<\/p>\n }<\/p>\n Postanowi\u0142em sprawdzi\u0107 szybko\u009c\u0107 dzia\u0142ania tych trzech algorytm\u00f3w, dla wyszukania liczb pierwszych z r\u00f3\u017cnych zakres\u00f3w, oto wyniki:<\/p>\n Dla n=1000:<\/p>\n Sito Eratostenesa<\/a>: 16ms<\/p>\n Sito liniowe: 16ms<\/p>\n M\u00f3j algorytm: 16ms<\/p>\n Wyniki identyczne, czyli algorytmy radza sobie r\u00f3wnie dobrze dla niewielkich liczb.<\/p>\n Dla n=10000:<\/p>\n Sito Eratostenesa<\/a>: 110ms<\/p>\n Sito liniowe: 78ms<\/p>\n M\u00f3j algorytm: 265ms<\/p>\n Tutaj ju\u017c wida\u0107 jak m\u00f3j algorytm odstaje wydajno\u009ccia od reszty, czego oczywi\u009ccie mo\u017cna by\u0142o si\u0119 spodziewa\u0107, po niskim stopniu skomplikowania.<\/p>\n Dla n=100000<\/p>\n\n\n
\n gdzie::<\/td>\n \u00a0p<\/em> jest najmniejsza liczba pierwsza dzielaca x<\/em> parzy\u009ccie,
\nk<\/em> \u2265 1,
\np<\/em> = q<\/em> lub p<\/em> jest mniejsze od najmniejszej liczby pierwszej, kt\u00f3ra dzieli q<\/em> parzy\u009ccie<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n