Divizorii și multiplii unui număr

În problemele de algoritmică apar foarte des două noțiuni:

divizorii unui număr;
multiplii unui număr.

Aceste noțiuni sunt baza multor exerciții de matematică și informatică.

Ce este un divizor?

Un număr d este divizor al lui n dacă n se împarte exact la d.

Cu alte cuvinte:

d este divizor al lui n dacă n % d == 0.

Exemplu pentru n = 12:

1 este divizor (12 % 1 = 0);
2 este divizor (12 % 2 = 0);
3 este divizor (12 % 3 = 0);
5 nu este divizor (12 % 5 = 2).

Ce este un multiplu?

Un număr m este multiplu al lui n dacă există un număr întreg k astfel încât:

m = n * k

Exemplu pentru n = 4:

4, 8, 12, 16, 20 sunt multipli ai lui 4;
10 nu este multiplu al lui 4.

Cum aflăm toți divizorii unui număr

Parcurgem toate valorile de la 1 la n și verificăm dacă împart exact pe n.

int n;
cin >> n;

for (int d = 1; d <= n; d++) {
    if (n % d == 0) {
        cout << d << " ";
    }
}

Input:
12

Output:
1 2 3 4 6 12

Observație utilă

Pentru orice n >= 1, numărul 1 este divizor.

Pentru n >= 2, există mereu cel puțin doi divizori evidenți: 1 și n.

Câți divizori are un număr

int n;
cin >> n;

int cnt = 0;
for (int d = 1; d <= n; d++) {
    if (n % d == 0) {
        cnt++;
    }
}

cout << cnt;

Input:
12

Output:
6

Cum generăm multiplii unui număr

Pentru a afișa primii k multipli ai lui n, putem folosi un for.

int n, k;
cin >> n >> k;

for (int i = 1; i <= k; i++) {
    cout << n * i << " ";
}

Input:
5 6

Output:
5 10 15 20 25 30

Multiplii lui `n` până la o limită

int n, limita;
cin >> n >> limita;

for (int x = n; x <= limita; x += n) {
    cout << x << " ";
}

Input:
4 25

Output:
4 8 12 16 20 24

Legătura dintre divizori și multipli

Dacă d este divizor al lui n, atunci:

n este multiplu al lui d.

Exemplu:

3 este divizor al lui 12;
12 este multiplu al lui 3.

Greșeli frecvente

1. Începem de la 0 când căutăm divizori

for (int d = 0; d <= n; d++) // GREȘIT

La d = 0, expresia n % d nu este permisă.

2. Confuzie între divizor și multiplu

d divide pe n -> d este divizor al lui n;
n se scrie d * k -> n este multiplu al lui d.

Cum verificăm rapid dacă m este multiplu al lui n?

Verificarea standard este:

m % n == 0, cu condiția n != 0.

3. Condiția greșită la verificare

if (n % d = 0) // GREȘIT

Corect:

if (n % d == 0)

Ce să reții

Un divizor al lui n împarte exact pe n.
Un multiplu al lui n are forma n * k.
Divizorii se caută, de obicei, în intervalul 1 ... n.
Multiplii se pot genera prin n, 2*n, 3*n, ....
Nu împărțim niciodată la 0.

Probleme

pbinfoSuma Divizori→

pbinfoSuma Divizorilor Impari→

pbinfoProduscifreimpare→