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 numerelor de la 1 la N (Folosind ciurul lui Eratostene)

Dându-se un număr natural n, să se afișeze pe ecran numărul de divizori al tuturor numerelor de la 1 la n.

Exemplu. Pentru n = 10, răspunsul este 1 2 2 3 2 4 2 4 3 4 (1 are 1 divizor, 2 are 2 divizori, 3 are 2 divizori, etc.).

Vom prezenta două metode, prima naivă și a doua folosind Ciurul lui Eratostene, modificat.

Metoda 1 (naivă)

O primă metodă constă în parcurgerea tuturor numerelor de la 1 la n și aflarea, folosind algoritmul de determinare a numărului de divizori, numărul divizorilor numărului curent.

Algoritmul este destul de intuitiv, însă nu este îndeajuns de eficient.

Implementare C++

#include <iostream>

using namespace std;

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

    //Parcurgem toate numerele de la 1 la n și determinăm divizorii fiecăruia
    //Mai multe detalii găsiți mai sus
    for(int i = 1; i <= n; i++) {
        int nrDiv = 0; //Numărul de divizori al numărului curent
        for(int d = 1; d * d <= i; d++) {
            if(i % d == 0) { //Am găsit un divizor
                nrDiv++;
                if(d != i / d) { //Perechea divizorului diferă de numărul în sine
                    nrDiv++;
                }
            }
        }
        cout << nrDiv << " ";
    }
    return 0;
}

Metoda 2 (ciurul lui Eratostene)

Ciurul lui Eratostene este un algoritm important care ia numeroase forme, însă la bază poate să determine pentru orice număr de la 1 la n, care sunt prime. Această lecție explică în detaliu cum funcționează algoritmul de bază.

Putem să adaptăm un pic algoritmul: pentru numărul curent i, vom aduna cu 1 numărul de divizori ai tuturor multiplilor lui i: i, 2 * i, 3 * i, ….

Practic, metoda aceasta, în loc să caute divizorii fiecărui număr (ca și în prima soluție), caută pentru fiecare număr multiplii acestuia, pe care îi marchează.

Vizualizarea algoritmului (animație)

Iată un exemplu, pentru n = 10:

Variabilă Valoare
i 12345678910
j (multiplii lui i) 1234567891024681036948510678910
ciur[1] 011
ciur[2] 01122
ciur[3] 01122
ciur[4] 0112233
ciur[5] 01122
ciur[6] 011223344
ciur[7] 01122
ciur[8] 011223344
ciur[9] 0112243
ciur[10] 011223344

Implementare în C++

#include <iostream>

using namespace std;

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

    //Ne declarăm ciurul
    int ciur[1001];
    for(int i = 1; i <= n; i++) //Golim șirul
        ciur[i] = 0;
    for(int i = 1; i <= n; i++) //Pentru toate numerele de la 1 la n
        for(int j = i; j <= n; j += i) //Luăm toți multipli numărului, mai mici sau egali cu n
            ciur[j]++;

    //Afișăm la final divizorii numerelor de la 1 la n
    for(int i = 1; i <= n; i++) {
        cout << ciur[i] << " ";
    }
    return 0;
}

Bibliografie sau alte resurse

  • PbInfo (algoritmi ciurul lui Eratostene)
  • 100din100 (lecție completă)
  • PbInfo (algoritmul de bază de ciur)

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

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