Liczby Pierwsze - algorytmy
Zajęcia 5
Liczby Pierwsze - algorytmy
Zajęcia 5
Liczby pierwsze i złożone
Liczba pierwsza
(z ang. prime number) – to liczba naturalna, która
posiada dokładnie dwa różne dzielniki – liczbę 1 oraz samą siebie.
Kilka kolejnych liczb pierwszych:
2, 3, 5, 7, 11, 13, 17, 19, 23
, itd.
Zbiór wszystkich liczb pierwszych oznacza się symbolem
P
.
Liczby naturalne większe od 1, które nie są pierwsze, nazywa się
liczbami złożonymi
.
Z podanych definicji wynika, że liczby
0
i
1
nie są ani pierwsze, ani
złożone.
Tw.
Każda liczba naturalna większa od 1 daje się jednoznacznie zapisać w
postaci iloczynu skończonego niemalejącego ciągu 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 są w pewnym sensie
atomami, z których przy pomocy mnożenia zbudowane są pozostałe
liczby.
Przykład:
120=2*3*4*5
960=2*2*3*4*4*5
Twierdzenie Euklidesa
Tw.
Zbiór wszystkich liczb pierwszych P
jest zbiorem nieskończonym.
Dowód:
Przypuśćmy, wbrew tezie, że zbiór wszystkich liczb pierwszych P
jest zbiorem
skończonym.
Niech
P={p
1
,p
2
,…,p
n
}, gdzie p
i
, dla i=1,2,…,n, to wszystkie kolejne liczby
pierwsze.
Rozważmy liczbę:
x=p
1
*p
2
*…*p
n
+1.
Zauważmy, że:
x/p
i
=p
1
*p
2
*…*p
i-1
*p
i+1
*…*p
n
+1/p
i
dla dowolnego i=1,2,…,n.
A zatem x nie dzieli się przez żadną liczbę ze zbioru P.
Mamy teraz dwie możliwości:
1) x jest liczbą pierwszą (wtedy jest ona różna od każdej liczby ze zbioru P, bo
x>p
i
dla dowolnego i=1,2,..,n),
2) x nie jest liczbą pierwszą (musi ją zatem dzielić jakaś liczba pierwsza p nie
będąca oczywiście w zbiorze P).
W każdym przypadku dostajemy dodatkową liczbę pierwszą leżącą poza
zbiorem P.
A zatem zbiór wszystkich liczb pierwszych P
jest zbiorem nieskończonym.
Test pierwszości
Liczbę n będziemy próbowali dzielić przez kolejne liczby naturalne z przedziału
od 2 do n-1. Jeśli któraś z tych liczb będzie dzieliła n bez reszty, to liczba n jest
liczbą złożoną (zatem nie pierwszą) i algorytm możemy zakończyć z wynikiem
negatywnym. Jeśli żadna z liczb od 2 do n-1 nie dzieli liczby n, to n jest liczbą
pierwszą. Algorytm kończymy z wynikiem pozytywnym.
Zadanie 1
Napisz program realizujący powyższy algorytm.
Generowanie wszystkich liczb pierwszych z przedziału
[2,n]
Zadanie 2
Napisz program realizujący powyższy algorytm.
źródło: http://edu.i-
lo.tarnow.pl/inf/utils/001_2008/0116.php
Generowanie kolejnych n liczb pierwszych
Zadanie 3
Napisz program realizujący powyższy algorytm.
źródło: http://edu.i-
lo.tarnow.pl/inf/utils/001_2008/0116.php
Praca domowa:
Zadanie
Istnieje prosty sposób poprawiający szybkość sprawdzania, czy dana liczba naturalna
n
jest pierwsza. A mianowicie, w celu sprawdzenia, czy dana liczba naturalna
n
jest
pierwsza wystarczy dzielić ją przez kolejne liczby naturalne ze zbioru
{2,3,…,
[sqrt(n)]}
, gdzie
[sqrt(n)]
– to część całkowita z liczby
sqrt(n)
. Napisz program
realizujący ten algorytm.