Probleme cu Divizibilitate

Cuprins

1. Divizorii unui număr întreg 2. Număr prim 3. Descompunerea în factori primi ai unui număr întreg 4. CMMDC:

a) Algoritmul lui Euclid(varianta cu resturi) b) Algoritmul lui Euclid(varianta prin scăderi repetate)

5. CMMMC

Probleme propuse: 1. Număr perfect 2. Număr deficient 3. Număr abundent

Teme de casă!

1. Divizorii unui număr întreg

Enunț: Se citește un număr întreg în variabila n. Scrieți un program C++ care

determină și afișează toți divizorii lui. Divizorii improprii ai unui număr sunt 1 și el

însuși, iar divizorii proprii sunt toți divizorii lui, înafară de 1 și el însuși.

Observație: Divizorii proprii ai unui număr se găsesc în intervalul [2,n/2]!

Exemplu: Dacă n=24, divizorii numărului 24 sunt: 1,2,3,4,6,8,12,24

i 2 3 4 5 6 7 8 9 10 11 12

...* 2 3 4 6 8 12

...*: se afișează

Regula este: dacă restul împărțirii lui n la i este 0(n%i==0)

atunci i este divizor a lui n și se afișează.

Soluție:

Program(proiect): divizorii_n

Temă de casă/Muncă independentă

Problema 1: Numărul divizorilor lui n (nr_divizori)

Enunț: Se citește un număr întreg în variabila n. Scrieți un program C++ care determină

numărul tuturor divizorilor lui n(se numără atât divizorii proprii, cât și divizorii improprii). Dacă

numărul n are exact 2 divizori, atunci n este număr prim și se va afișa mesajul ”Prim”, în caz

contrar se va afișa mesajul cu numărul divizorilor lui n.

Observație: Dacă numărul divizorilor lui n rămâne 2, atunci numărul este prim!

Exemplu: Dacă n=24, divizorii numărului sunt: 1,2,3,4,6,8,12,24, deci se va afișa valoarea 8.

i 2 3 4 5 6 7 8 9 10 11 12

k 2 3 4 5 6 7 8

Problema 2: (suma_divizori)

Enunț: Se citește un număr întreg în variabila n. Scrieți un program C++ care calculează suma

tuturor divizorilor lui n(se numără atât divizorii proprii, cât și divizorii improprii). Programul va

afișa următorul mesaj: dacă s=2n atunci n este număr perfect, dacă s<=2n atunci n este

număr deficient, iar dacă s>=2n atunci n este număr abundent.

Exemplu: Dacă n=28, divizorii numărului sunt: 1,2,4,7,14,28, suma divizorilor este 56, deci n

este număr perfect.

Temă de casă/Muncă independentă

Problema 3: (nr_subperfect)

Temă de casă/Muncă independentă

Un număr natural nenul se numește subperfect dacă este strict mai

mic decât suma divizorilor săi proprii (divizori naturali diferiți de 1 și de

el însuși). Exemplu: 12 este număr subperfect pentru că

12<2+3+4+6.

Se citesc două numere naturale a și b (2≤a<b≤109) și se cere să se

afișeze, separate prin câte un spațiu, în ordine descrescătoare, toate

numerele subperfecte din intervalul [a,b]. Dacă în interval nu există

astfel de numere, se afișează mesajul nu exista.

Exemplu: pentru a=10 și b=20 se afișează: 20 18 12

a) Scrieți în C++ programul de rezolvare pentru problema enunțată.

b) Menționați rolul tuturor variabilelor care au intervenit în algoritmul

realizat la punctul a) și indicați datele de intrare, respectiv datele de

ieșire ale problemei enunțate.

Număr prim

Enunț: Se citește de la tastatură un număr natural în variabila x(x≠0, x≠1). Scrieți un program în C/C++ care verifică dacă numărul citit este prim sau nu, afișând un mesaj corespunzător. Observație: Un număr natural este număr prim dacă nu are niciun divizor propriu(adică nici un divizor diferit de 1 și el însuși)! De aceea, se exclud căutările divizorilor numărului pentru cazurile în care valoarea numărului este mai mică decât 2; dacă numărul este chiar 2(este singurul număr prim par) atunci numărul este prim, iar dacă este par din nou numărul nu mai poate fi prim! După toate aceste cazuri, se încep căutările pornind cu valoarea 3 a divizorului. Soluție: true=1; false=0;

Soluția

Descompunerea în factori primi ai unui număr întreg

Enunț: Se citește de la tastatură un număr natural în variabila n(x≠0,

x≠1). Scrieți un program în C/C++ care afișează descompunerea în

factori primi a lui n.

Exemplu: Dacă n=36 atunci descompunerea în factori primi va fi:

2^2*3^2

n d p 36 2 1

18 2 2

9 3 1

3 3 2

1

Soluția Program: factor_prim

CMMDC(a,b) – Algoritmul lui Euclid(varianta cu resturi)

Enunț: Se citesc de la tastatură două numere întregi în variabilele a și b. Scrieți un

program C++ care determină cel mai mare divizor comun al lor.

Program: cmmdc_1

CMMDC(a,b) – Algoritmul lui Euclid(varianta prin scăderi repetate)

Enunț: Se citesc de la tastatură două numere întregi în variabilele a și b. Scrieți un

program C++ care determină cel mai mare divizor comun al lor.

Program: cmmdc_2

Muncă independentă/Temă de casă Problema 1: CMMMC(a,b)

Enunț: Se citesc de la tastatură două numere întregi în variabilele a și b. Scrieți un

program C++ care determină cel mai mic multiplu comun al lor.

Regulă: CMMMC = a*b/CMMDC