Algorytmy na liczbach

Algorytmy na liczbach

naturalnych

naturalnych

Faktoryzacja liczby naturalnej – zapis

Faktoryzacja liczby naturalnej – zapis

liczby w postaci iloczynu liczb

liczby w postaci iloczynu liczb

pierwszych

pierwszych

Zapis liczby w postaci iloczynu

Zapis liczby w postaci iloczynu

liczb pierwszych

liczb pierwszych

Liczby pierwsze

to te liczby naturalne większe od 1, które

mają tylko dwa dzielniki naturalne: jedynkę i samą siebie

np.

2, 3, 5, 7, 11,…

2 = 1 *
2
3 = 1 *
3
5 = 1 *
5
7 = 1 *
7
11 = 1 *
11

Zapis liczby w postaci iloczynu

Zapis liczby w postaci iloczynu

liczb pierwszych

liczb pierwszych

Daną liczbę naturalną

n

możemy przedstawić w postaci

iloczynów:

n= p1 * p2 * … * pi          p1<=p2<= … <=pi

gdzie

p1

do

pi

to kolejne liczby pierwsze

2, 3, 5, 7

…

Jeśli znajdziemy liczbę pierwszą, która dzieli liczbę

n

bez

reszty, to znaczy, że

p

jest dzielnikiem

n

.

1. Liczbę

n

dzielimy przez

p

dopóty, dopóki wynik będzie

całkowity

(

kończymy gdy

n mod p<>0).

2. Jeśli

n

nie dzieli się bez reszty przez

p

, to zwiększamy

p

-

bierzemy kolejną liczbę naturalną.

3. Jeśli liczba

n

nie jest podzielna przez wszystkie podzielniki

p < n

, to

n

jest liczbą pierwszą.

np. 24=2 * 2 * 2 * 3

Zapis liczby w postaci iloczynu

Zapis liczby w postaci iloczynu

liczb pierwszych

liczb pierwszych

Możemy sformułować następującą własność:

Jeśli

n

nie jest liczbą pierwszą, to ma czynnik

p

spełniający

warunek

p<=

.

Ponadto każda liczba złożona ma w swoim rozkładzie na dwa
czynniki, co najwyżej jeden czynnik większy niż
Gdyby liczba złożona miała dwa czynniki większe od , to
ich iloczyn byłby większy od

n

, co oznaczałoby sprzeczność.

n

n

n

Faktoryzacja liczby naturalnej

Faktoryzacja liczby naturalnej

-lista kroków

-lista kroków

Specyfikacja

Dane

:

n

- liczba naturalna

Wynik

:

p1, p2, ..., pi

dzielniki liczby

n

Krok1

.

Wczytaj liczbę

n, p:=2;

Krok2

.

Jeśli

n=1

,

przejdź do

kroku 5.

Krok3

.

Dopóki

p<n

wykonuj operacje:

c:= n div p

;

r:=n mod p

oraz wykonuj

krok 4

;

Krok4

.

jeśli

r=0

wypisz

p

i

n:=c

w przeciwnym razie

p

zwiększ o

1 (wróć do kroku

3)

Krok5

.

Zakończ algorytm.

Zmienne pomocnicze:

C

- całość z dzielenia

n

przez

p
r

- reszta z dzielenia

n

przez

p

Schemat blokowy

Schemat blokowy

START

Wprowadź (n)

i:=2;

i <= n

r=0

n=12, i=2

KROK I

2<=12

Tak

krok a)

c=12 div 2=6;

r= 12 mod 2=0;

0=0

Tak

wypisz

2

n=6

krok b)

c=6 div 2=3;

r= 6 mod 2=0
0=0

Tak

wypisz

2

n=3

krok c)

c= 3 div 2=1

r=3 mod 2=1
1=0

Nie

i=2+1=3

KROK II

3<=3

Tak

krok a)

c=3 div 3=1

r= 3 mod 3=0
0=0

Tak

wypisz 3
n=1

krok b)

c=1 div 3 =0

r= 1 mod 3=1
1=0

Nie

i:=3+1=4

KROK III

4<=1

Nie

Koniec

n:=c

NIE

STOP

TAK

c:=n div i

r:=n mod i

TAK

Wypr (i)

NIE

i:=i+1

Zadania

Zadania

Zadanie1

Napisz program przedstawiający liczbę

n

w postaci iloczynu liczb

pierwszych n- elementowej. Liczbę n wprowadzamy z klawiatury.

Zadanie2

Zmodyfikuj program z

zadania1

, tak aby w przypadku wprowadzenia za

liczbę

n

liczby pierwszej, pojawiał się komunikat :

„Liczba pierwsza – brak czynników mniejszych od

n

”