Question

Cerința
Se dă un număr natural n. Să se determine numărul din intervalul [1,n] care are număr maxim de divizori. Dacă există mai multe asemenea numere, se va afișa cel mai mic dintre ele.

Date de intrare
Programul citește de la tastatură numărul n.

Date de ieşire
Programul va afișa pe ecran valoarea cerută.

Restricții și precizări
0 < n <= 100.000



Exemplu
Intrare

20
Ieșire

12
Explicații:
12, 18 şi 20 au număr maxim de divizori, dar 12 este cel mai mic.
-------Ideea mea------
Ma gandeam sa determin nr de divizori ai ultimului numar(20) si dupa sa scad cate 1 (19 18 17 16) si sa verifiic daca au acelasi nr de divizori daca un numar are atunci va primi min dar nu stiu cum ar trebuii sa fac programul sa se opreasca acolo(val 12).Nu cred ca ideea mea este foarte buna avand in vedere timpul rularii programului.
Va rog daca se poate sa imi rezolvati problema in orice mod considerati dv ca algoritmul este bun dar daca se poate sa imi si explicati ce se intampla in cod.
Multumesc!!!

Answer 1

Solutia asta are 100p. Ceea ce fac in cod e destul de simplu: iau numere de la 1 la n, daca numarul lor de divizori e mai mare (nu "mai mare sau egal" pentru ca vrem numarul MINIM cu un numar maxim de divizori -  "se va afișa cel mai mic dintre ele.") decat maximul precedent modific maximul si continui.
Ca sa fie mai rapid totul, nu calculez numarul de divizori pana la n sau n/2, ci pana la sqrt(n), iar asta nu afecteaza comparatiile (pentru ca toate numerele de divizori vor fi mai mici, nu doar cateva). Daca as fi avut nevoie de valoare lor exacta (deci nu doar pentru a verifica daca nrDiv(a) >b) nu as fi facut asa, dar pentru ca nu e nevoie am ales varianta asta ceva mai rapida.

#include <iostream>

using namespace std;

// Numarul de divizori pana la sqrt(n), pentru eficienta
int nrDiv(int n)
{
    int nr = 0;
    for (int i=2; i*i <= n; i++)
        if (n%i == 0)
            nr ++;
    return nr;
}

int main()
{
    /**
     * maxDiv = numarul de divizori maxim
     * maxNr = numarul cu maxDiv divizori, care va fi afisat
     */
    int n, maxDiv = 1, maxNr = 1;
    cin >> n;
    for (int i=1; i<=n; i++)
    {
        // Ca sa nu il calculam de doua ori
        int nr = nrDiv(i);

        if (nr > maxDiv)
        {
            maxDiv = nr;
            maxNr = i;
        }
    }
    cout << maxNr;
    return 0;
}