Se citeşte un număr natural n şi apoi un şir de n numere întregi. Afişaţi primul număr care are cei mai mulți divizori. 12

Pentru a rezolva această problemă, putem parcurge șirul de numere și pentru fiecare număr vom calcula numărul de divizori și îl vom compara cu cel mai mare număr de divizori găsit până la momentul respectiv. Dacă numărul de divizori este mai mare, vom actualiza valoarea maximă și numărul corespunzător.

Iată un posibil program în limbajul C++ care implementează această idee:

#include <iostream>

#include <cmath>

int main() {

    int n;

    std::cout << „Introduceti numarul de elemente: „;

    std::cin >> n;

    int max_divisors = 0;

    int max_divisors_num = 0;

    for (int i = 0; i < n; i++) {

        int num;

        std::cout << „Introduceti numarul ” << i + 1 << „: „;

        std::cin >> num;

        int divisors = 0;

        for (int j = 1; j <= std::sqrt(num); j++) {

            if (num % j == 0) {

                divisors += 2; // Adaugăm 2 divizori pentru fiecare pereche j și num / j

            }

            if (j * j == num) {

                divisors–; // Scoatem un divizor pentru cazul în care j == num / j

            }

        }

        if (divisors > max_divisors) {

            max_divisors = divisors;

            max_divisors_num = num;

        }

    }

    std::cout << „Primul numar cu cei mai multi divizori este ” << max_divisors_num << ” si are ” << max_divisors << ” divizori.\n”;

    return 0;

}

Explicații:

• În primul rând, citim de la tastatură numărul de elemente din șir.
• Inițializăm variabilele max_divisors și max_divisors_num cu valoarea 0.
• Parcurgem șirul de numere folosind o buclă for.
• Pentru fiecare număr, calculăm numărul de divizori. Parcurgem toate numerele între 1 și radicalul pătrat din număr (acesta fiind cel mai mare posibil divizor al său), și dacă găsim un divizor, adăugăm 2 la numărul total de divizori (deoarece avem o pereche de divizori), și scoatem unul dacă divizorul este egal cu radicalul pătrat din număr (deoarece am numărat deja această pereche înainte).
• Comparam numărul de divizori al numărului curent cu valoarea maximă găsită până la momentul respectiv, și actualizăm variabilele max_divisors și max_divisors_num dacă este cazul.
• La final, afișăm numărul cu cei mai mulți divizori și numărul acestora.

Notă: Acest program are o complexitate O(n * sqrt(m)), unde m este cel mai mare număr din șir