#262 · Subiectul II · Programare

Numărul cu cei mai puțini divizori primi dintr-un șir terminat cu 0

✓ Rezolvare explicatăTeleorman 2026 · nr. 22

Enunț

Se citesc numere naturale până când se citește numărul 0. Să se afișeze care dintre numerele citite are număr minim de divizori primi. Dacă există mai multe numere cu același număr minim de divizori, se va afișa doar ultimul dintre ele.

Exemple

Date de intrare	Date de ieșire	Explicații
`6 8 2 4 10 12 7 9 16 0`	`16`	8, 2, 4, 7, 9, 16 au câte un divizor prim; ultimul e 16
`6 10 15 0`	`15`	toate au doi divizori primi
`3 4 1 6 9 0`	`1`	1 nu are niciun divizor prim

⚠️ Exemplul oficial e greșit: pentru 6, 8, 2, 4, 10, 12, 7, 9, 16 subiectul afișează 9. Divizorii primi sunt: 6 → {2, 3}, 8 → {2}, 2 → {2}, 4 → {2}, 10 → {2, 5}, 12 → {2, 3}, 7 → {7}, 9 → {3}, 16 → {2}. Minimul e 1, iar ultimul număr cu un singur divizor prim e 16, nu 9. Nici numărarea factorilor cu repetiție (16 = 2⁴ are patru) nu dă 9 — ar da 7. În plus, exemplul nu arată 0-ul care încheie citirea.

Rezolvare

C++

#include <iostream>
using namespace std;

int nrDivPrimi(int n) {
    int cnt = 0;
    for (int d = 2; d * d <= n; d++)
        if (n % d == 0) {
            cnt++;
            while (n % d == 0)
                n /= d;
        }
    if (n > 1) cnt++;
    return cnt;
}

int main() {
    int x, rez = -1, minim = 100;
    cin >> x;
    while (x != 0) {
        int k = nrDivPrimi(x);
        if (k <= minim) {            // <= : la egalitate retinem ultimul
            minim = k;
            rez = x;
        }
        cin >> x;
    }
    cout << rez;
    return 0;
}

Exersează mai departe

Probleme cu aceeași tehnică

#043ProgramareSă se calculeze şi să se afişeze cel mai mare divizor comun al elementelor vectorului #044ProgramareCel mai mare divizor comun a două numere, folosind o funcție recursivă #047ProgramareSă se afişeze două numere naturale prime a căror sumă este numărul n #064ProgramareSă se afişeze numărul valorilor prime din vector #066ProgramareSă se afişeze toate numerele mai mici sau egale cu n, care au exact 3 divizori #068ProgramareSă se afişeze numărul elementelor care sunt numere palindrom