Lectia 14

De la matematică putem spune că un număr natural d este divizorul lui n, dacă şi numai dacă, restul împărţirii lui n la d este egal cu zero:

┌dacă n % d = 0 atunci

│ scrie d „îl divide pe” n

│altfel

│ scrie d „nu îl divide pe ” n

└■

Dacă vom nota cu D_n mulţimea divizorilor numărului n atunci dacă n=12 putem scrie: D₁₂={1, 2, 3, 4, 6, 12}, unde 1 şi 12 se numesc divizori improprii ai lui 12, iar 2, 3, 4, 6 sunt divizorii proprii ai lui 12.

Algoritmul pentru determinarea(afisarea) divizorilor unui număr n dat de la tastatură este:

citeşte n (număr natural)

scrie “Divizorii numărului ”, n, “sunt:”

┌pentru d=1, n, +1

│ ┌dacă n%d=0 atunci

│ │ scrie d, ” ”

│ └■

└■

Algoritmul pentru determinarea divizorilor proprii a unui număr n, dat de la tastatură este:

citeşte n (număr natural)

scrie “Divizorii proprii a numărului ”, n, “sunt:”

┌pentru d=2, n/2, +1

│ ┌dacă n%d=0 atunci

│ │ scrie d, ” ”

│ └■

└■

Un număr natural care are exact doi divizori se numeşte număr prim, iar numerele naturale care nu sunt numere prime se numesc numere compuse. Plecând de la această definiţie, algoritmul care verifică dacă numărul natural n, dat de la tastatură este prim are următoarea formă :

citeşte n (număr natural)

nr=0

┌pentru d=1,n,+1

│ ┌dacă n%d=0 atunci

│ │ nr=nr+1

│ └■

└■

┌dacă nr=2 atunci

│ scrie n, ”este număr prim”

│altfel

│ scrie n, ”nu este număr prim”

└■

Matematic s-a demonstrat că, dacă numărul n nu are nici un divizor propriu mai mic sau egal cu radical din x, atunci numărul este prim. Folosind această operaţie se micşorează numărul de paşi în a verifica dacă n este prim sau nu. Algoritmul în acest caz se poate scrie şi aşa:

citeşte n (număr natural)

ok=1 // presupun numărul dat ca fiind un număr prim

d=2

┌cât timp d<=radical din x şi ok = 1 execută

│ ┌dacă n%d=0 atunci // am găsit un divizor propriu în [2,radical din x]

│ │ ok=0 // atunci n nu este prim

│ │altfel

│ │ d=d+1

│ └■

└■

┌dacă ok = 1 atunci

│ scrie n, ”este număr prim”

│altfel

│ scrie n, ”nu este număr prim”

└■

Observaţie:

a. numărul 1 nu este număr prim, dar nu este nici număr compus;

b. numărul 2 este singurul număr prim şi par.