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

”