Liczby pierwsze

Często spotykamy się z problemem znalezienia w danym przedziale wszystkich liczb pierwszych. Można to łatwo zrobić sprawdzając po kolei każdą z nich, czy jest złożona. Rozwiązanie to jednak nie byłoby efektywne. Jest inna, szybsza metoda rozwiązanie tego problemu. Jest to tzw. "sito Eratostenesa". Nazwa pochodzi od tego, że wszystkie liczby są po kolei przesiewane i usuwane są wszystkie wielokrotności danej liczby.

Aby znaleźć wszystkie liczby do 1 do N, wypisuje się je kolejno. Liczba 2, pierwsza z wypisanych liczb, jest liczbą pierwszą; pozostawia się ją i wykreśla się wszystkie dalsze liczby podzielne przez 2, gdyż nie są to liczby pierwsze. Z liczb pozostałych po tym wykreśleniu kolejną po liczbie 2 jest liczba 3. Pozostawia się ją jako liczbę pierwszą i wykreśla się wszystkie dalsze liczby podzielne przez 3, które nie zostały poprzednio wykreślone. Z pozostałych teraz liczb kolejną po 2 i 3 jest liczba 5; pozostawia się ją i wykreśla wszystkie dalsze liczby podzielne przez 5, które nie zostały dotychczas wykreślone. Pod dalszą uwagę bierze się liczby p nie większe od pierwiastka z N. Kontynuując to wykreślanie, dojdzie się wreszcie do tego, że wszystkie liczby, które nie są pierwsze zostaną wykreślone, pozostaną tylko liczby pierwsze nie większe od N .

Żeby wszystko stało się jaśniejsze przejdźmy do przykładu, który jest przedstawiony obok w komórce dla N=100.

	Podstawowe własności: - najmniejsą liczbą pierwszą jest 2, - największa liczba pierwsza nie istnieje, - dla dowolnej liczby naturalnej n>1, między liczbami n i 2n istnieje conajmniej jedna liczba pierwsza, - dla dowolnej liczby natutalnej n>6, między liczbami n i 2n znajdują się conajmniej dwie liczby pierwsze: conajmniej jedna postaci 2k+1; i conajmniej jedna postaci 4m+1.
Twierdzenie: tzn. ''Jest więcej liczb pierwszych, niż w każda dana liczba [skończona] liczb pierwszych'' Zatem tw może równie dobrze brzmieć: Żaden skończony zbiór nie zawiera wszystkich liczb pierwszych. Twierdzenie to zostało udowodnione mi. przez Euklidesa. Dowód znajduje się obok.
Sito Eratostenesa do wyszukiwania liczb pierwszych:	Często spotykamy się z problemem znalezienia w danym przedziale wszystkich liczb pierwszych. Można to łatwo zrobić sprawdzając po kolei każdą z nich, czy jest złożona. Rozwiązanie to jednak nie byłoby efektywne. Jest inna, szybsza metoda rozwiązanie tego problemu. Jest to tzw. "sito Eratostenesa". Nazwa pochodzi od tego, że wszystkie liczby są po kolei przesiewane i usuwane są wszystkie wielokrotności danej liczby. Aby znaleźć wszystkie liczby do 1 do N, wypisuje się je kolejno. Liczba 2, pierwsza z wypisanych liczb, jest liczbą pierwszą; pozostawia się ją i wykreśla się wszystkie dalsze liczby podzielne przez 2, gdyż nie są to liczby pierwsze. Z liczb pozostałych po tym wykreśleniu kolejną po liczbie 2 jest liczba 3. Pozostawia się ją jako liczbę pierwszą i wykreśla się wszystkie dalsze liczby podzielne przez 3, które nie zostały poprzednio wykreślone. Z pozostałych teraz liczb kolejną po 2 i 3 jest liczba 5; pozostawia się ją i wykreśla wszystkie dalsze liczby podzielne przez 5, które nie zostały dotychczas wykreślone. Pod dalszą uwagę bierze się liczby p nie większe od pierwiastka z N. Kontynuując to wykreślanie, dojdzie się wreszcie do tego, że wszystkie liczby, które nie są pierwsze zostaną wykreślone, pozostaną tylko liczby pierwsze nie większe od N . Żeby wszystko stało się jaśniejsze przejdźmy do przykładu, który jest przedstawiony obok w komórce dla N=100.