Contact și feedback

Nu obții 100 de puncte sau ai nelămuriri în privința problemelor? Scrie-mi pe Instagram.


Ai găsit o greșeală, vrei să raportezi un utilizator sau vrei să comunici altceva? Folosește formularul de contact.


Vrei să ne transmiți o părere despre platformă? Folosește formularul de feedback.

Shortcuturi

Folosește următoarele shortcuturi pentru a naviga mai ușor pe platformă.

Generale

Meniu shortcuturi?
Căutare probleme sau utilizatori/
Navigare printre rezultatele căutării↑, ↓
Meniu de contact și feedbackCTRL + Shift + F
Ieșire din meniuriEsc

Editor probleme

Setări editorCTRL + Shift + S
Schimbare stil editorCTRL + Shift + E
Șabloane de codCTRL + Shift + 1/2/3
Golire editorCTRL + Shift + 4

Numărul de divizori al unui număr în C++

Dându-se un număr natural n, să se afle numărul său de divizori.

Exemplu. Pentru n = 20, numărul de divizori este 6 (divizorii acestuia sunt: 1, 2, 4, 5, 10, 20).

Metoda 1 (naivă)

Știm că toți divizorii unui număr se află între 1 și numărul respectiv. Așadar, putem să parcurgem toate numerele d de la 1 la n și să verificăm dacă numărul curent (d) este divizor al lui n (n % d == 0).

Implementare C++

#include <iostream>

using namespace std;

int main()
{
    //Declarăm și citim numărul n
    int n;
    cin >> n;

    //Calculăm numărul de divizori ai lui n
    int nrdiv = 0;
    for(int d = 1; d <= n; d++) {
        if(n % d == 0) { //Am găsit un nou divizor pentru n
            nrdiv++;
        }
    }

    //Afișăm numărul de divizori ai lui n
    cout << nrdiv;
    return 0;
}

Observații

Acest algoritm nu este foarte bun, deoarece parcurge toate numerele de la 1 la n. Spre exemplu, pentru n = 1.000.000.000, se fac un miliard de operații, deși numărul 1.000.000.000 are doar 100 de divizori.

Din fericire, există o metodă mai eficentă.

Metoda 2 (eficientă)

Observăm că divizorii vin în perechi. Dacă d este divizor al lui n, atunci n / d este un număr natural, așadar n / d este un alt divizor al lui n (putem verifica asta calculând d * (n / d) = n).

Mai mult decât atât, divizorii sunt în jurul numărului sqrt(n) — dacă d < sqrt(n), atunci n / d > sqrt(n). Astfel, trebuie să parcurgem numerele doar până la radicalul lui n, considerând atât d, cât și n / d ca și divizori.

Există totuși o excepție: numerele pătrate perfecte. De obicei, numerele au un număr par de divizori (din acest motiv vin în perechi), însă excepție fac pătratele perfecte, unde există un d = sqrt(n). În acest caz, perechea lui d este n / d = n / sqrt(n) = sqrt(n) = d (d este perechea sa). În acest sens, pentru numerele pătrate perfecte, trebuie avut grijă să nu marcăm de două ori radicalul.

Implementare în C++

#include <iostream>
#include <cmath> //Pentru funcția sqrt(), ce extrage rădăcina pătrată a unui număr

using namespace std;

int main()
{
    //Declarăm și citim numărul n
    int n;
    cin >> n;

    //Calculăm numărul de divizori ai lui n
    int nrdiv = 0;
    for(int d = 1; d <= sqrt(n); d++) {
        if(n % d == 0) { //Am găsit doi divizori pentru n: d și n / d
            nrdiv++; //Marcăm divizorul d
            if(d != n / d) { //Dacă d nu este radical din n (d nu este perechea sa)
                nrdiv++; //Marcăm perechea lui d, n / d
            }
        }
    }

    //Afișăm numărul de divizori ai lui n
    cout << nrdiv;
    return 0;
}

Cuprinsul lecției

Se încarcă…

Citește și

Aria unui triunghi folosind coordonatele acestora în C++Cum să calculezi instant 2 la puterea N în C++Pointer în C++. Variabile de tipul char * (char steluță)Cel mai frecvent element dintr-un șir în C++Instrucțiunea continue (structuri repetitive)Rădăcina cubică a unui număr în C++ (cube root)Vectori de frecvență (de apariții) în C++Cum să afișezi partea întreagă a unui număr real în C++Aria și circumferința unui cerc în C++Șiruri de caractere în C++. Tot ce trebuie să știiCombinatorică în C++: permutări, aranjamente, combinări și alteleTransformarea unui număr din baza 10 în baza 2 în C++Interclasarea a doi vectori în C++Funcții predefinite în C++ (matematice, șiruri de caractere)Verifică dacă un număr dat este o putere de 2 în C++Mediana unui șir de valori în C++Maximul și minimul a n valori în C++Cifra maximă a unui număr recursiv în C++Oglinditul recursiv al unui număr în C++Numărul minim de peroane pentru o gară în C++Numărul combinărilor în C++ (formula combinărilor)Ce înseamnă variabilă globală și locală în C++?Maximul și minimul a trei valori în C++Numărul permutărilor în C++ (formula permutărilor)Aflarea sumei primelor N sume GaussValoarea absolută (modulul) unui număr în C++Verificare dacă un număr este palindrom în C++Distanța dintre două puncte în C++Indicatorul lui Euler în C++Afișarea elementelor unui vector recursiv în C++Suma numerelor naturale dintr-un interval dat în C++Do while vs while în C++ - Care e diferența?Transformarea unui număr din baza 2 în baza 10 în C++Algoritm recursiv pentru căutare binară (clasa a X-a)Bordarea unei matrice în C++Instrucțiunea for (structuri repetitive)Vectorii în C++: citire și afișareNumărul de cifre ale factorialului unui numărDivide et Impera (metodă de programare C++)Generarea șirului Fibonacci generalizat în C++Transformarea unei litere mari în literă mică în C++Tipul struct în C++. Ce sunt structurile de date neomogeneCel mai semnificativ bit în C++Instrucțiunea de decizie în C++: if, else, switch, caseVerificare număr prim în C++ (Clasa a IX-a)Suma divizorilor unui număr în C++Numărul de divizori al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Radicalul unui număr în C++ (rădăcina pătrată)Șirul lui Fibonacci în C++Ce înseamnă endl în C++?Instrucțiunea break (structuri repetitive)Inversarea unui șir de caractere în C++Ridicarea la putere în timp logaritmic în C++. Exponențiere rapidăIndicatorul lui Euler al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Verifică dacă un bit de pe o anumită poziție este 1 sau 0 în C++Cifrele unui număr. Prelucrarea cifrelor unui număr în C++Cel mai mare divizor comun (CMMDC) a două numere în C++Al N-lea termen dintr-o progresie geometricăSortare crescătoare recursivă în C++ - Merge sort și Bubble sortComplexitatea unui algoritm (timp și spațiu) în C++Vectorii în C++: declarare și parcurgereCMMDC recursiv a două numere naturale în C++Numărul de apariții al unui număr într-un vector în C++Verificarea unui an bisect în C++Cea mai lungă secvență de elemente crescătoare în C++Maximul și minimul unui vector în C++Verifică dacă o literă este mică sau mare în C++Verifică dacă un caracter este cifră în C++Funcții în C++. Ce sunt subprogrameleMaximul și minimul a două valori în C++Numărul de divizori al unui număr în C++De ce cer unele probleme răspunsul modulo 666013 sau modulo 1.000.000.007?Tipuri de date în C++: numere întregi, reale, caractere și alteleMatrice în C++. Declararea și parcurgerea tablourilor bidimensionaleAl N-lea termen dintr-o progresie aritmeticăTutorial instalare CodeBlocks (ușor) - Introducere în informatică C++Verifică dacă un număr aparține șirului Fibonacci în C++Cel mai mic număr cu suma cifrelor N în C++Codul ASCII (tabel complet)Citește un șir de caractere cu spații în C++Căutare binară în C++Aplicații cu ciurul lui Eratostene în C++: suma divizorilor, numărul divizorilorVerificare dacă șir de caractere este palindrom în C++Cel mai mic/mare divizor prim al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Matrice Fibonacci - al n-lea termen Fibonacci în timp logaritmicVerifică dacă un caracter este literă în C++Matrice pătratice în C++. Diagonala principală și secundarăCel mai puțin semnificativ bit în C++Operații cu numere mari în C++ - Toate funcțiile explicateCe este o funcție void în C++?Suma divizorilor numerelor de la 1 la N (Folosind ciurul lui Eratostene)Cifra maximă și minimă a unui număr în C++Suma elementelor unui vector recursiv în C++Al N-lea termen Fibonacci în C++CMMMC a două numere în C++ (cel mai mic multiplu comun)Structuri repetitive (while, do while, for, etc)Instrucțiunea do while (structuri repetitive)Calculul combinărilor de n luate câte k (nCk) în C++Numărul aranjamentelor în C++ (formula aranjamentelor)Instrucțiunea while (structuri repetitive)Inversarea unui vector în C++Află secolul unui an citit de la tastatură în C++Câte numere naturale sunt într-un interval dat? (C++)Materia pentru olimpiada de informatică - tot ce trebuie să știiFactorialul unui număr în C++Verifică dacă un număr este par sau impar fără modulo în C++Suma 1 + 2 + 3 + ... + N în C++Prima cifră a unui număr în C++Verifică dacă trei puncte sunt coliniare C++Ce este o variabilă unsigned în C++?Transformarea unei litere mici în literă mare în C++Numere triunghiulare. Verificarea unui număr triunghiularInterschimbarea a două variabile în C++ (3 metode)Verifică dacă o literă este vocală în C++Cifra de control a unui numărRecursivitate în C++Ciurul lui Eratostene în C++Numărul de divizori primi ai unui număr în C++Comentarii în C++Copiuțe: Cifrele unui numărAfișarea divizorilor primi ai unui număr în C++Oglinditul unui număr în C++Cum să citești și să afișezi în fișiere în C++Citirea și afișarea matricelor în C++

© Drepturi de autor

Echipa InfoAs își rezervă drepturile de autor pentru conținutul acestei pagini. Copierea conținutului fără acordul scris expres al InfoAs reprezintă o încălcare a Legii 8/1996 și va fi tratată ca atare.

Trimite lecția

Toată lecția

Doar videoclipul pe YouTube

Informatica devine ușoară cu InfoAs

Intră în cont