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;
}

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

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