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.