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

Suma divizorilor unui număr în C++

Dându-se un număr natural n, să se afle suma divizorilor săi.

Exemplu. Pentru n = 20, suma divizorilor este 42 (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 suma divizorilor lui n
    int sumdiv = 0;
    for(int d = 1; d <= n; d++) {
        if(n % d == 0) { //Am găsit un nou divizor pentru n
            sumdiv = sumdiv + d;
        }
    }

    //Afișăm suma divizorilor lui n
    cout << sumdiv;
    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 suma divizorilor lui n
    int sumdiv = 0;
    for(int d = 1; d <= sqrt(n); d++) {
        if(n % d == 0) { //Am găsit doi divizori pentru n: d și n / d
            sumdiv = sumdiv + d; //Adunăm divizorul d
            if(d != n / d) { //Dacă d nu este radical din n (d nu este perechea sa)
                sumdiv = sumdiv + n / d; //Adunăm perechea lui d, n / d
            }
        }
    }

    //Afișăm suma divizorilor lui n
    cout << sumdiv;
    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

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