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

Aplicații cu ciurul lui Eratostene în C++: suma divizorilor, numărul divizorilor

Ce este ciurul lui Eratostene

Ciurul lui Eratostene este un algoritm de determinare a tuturor numerelor prime de la 1 până la o anumită valoare, n. Algoritmul este foarte util, iar în această lecție am văzut cum funcționează și l-am implementat în C++.

În această lecție abordăm alte ciururi derivate din ciurul lui Eratostene. Majoritatea aplicațiilor țin de multiplii sau de divizorii unui număr și au o formă foarte asemănătoare.

Numărul de divizori al numerelor de la 1 la n

Algoritmul ia toate numerele de la 1 la n, iar mai apoi toți multiplii lor. Pentru fiecare multiplu în parte, creștem numărul de divizori cu 1. Citește aici explicațiile complete.

#include <iostream>

using namespace std;

//Ne declarăm ciurul
int ciur[1001];

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

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

Suma divizorilor numerelor de la 1 la n

Algoritmul ia toate numerele de la 1 la n, iar mai apoi toți multiplii lor. Pentru fiecare multiplu în parte, creștem suma divizorilor cu i. Citește aici explicațiile complete.

#include <iostream>

using namespace std;

//Ne declarăm ciurul
int ciur[1001];

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

    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] += i;

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

Cel mai mic divizor prim al numerelor de la 1 la n

Algoritmul asumă pentru început că răspunsul pentru fiecare număr în parte este chiar el însuși. După aceea, se caută divizorii primi ai fiecăruia și se modifică rezultatele. Citește aici explicațiile complete.

#include <iostream>

using namespace std;

//Ne declarăm ciurul
int ciur[1001];

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

    for(int i = 1; i <= n; i++)
        ciur[i] = i; //La început, asumăm că elementul i are cel mai mic divizor prim pe el însuși

    for(int i = 2; i <= n; i++) //Pentru toate numerele de la 2 la n
        if(ciur[i] == i) { //Elementul i este prim
            for(int j = 2 * i; j <= n; j += i) //Luăm toți multipli numărului, mai mici sau egali cu n
                if(ciur[j] == j)
                    ciur[j] = i;
        }

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

Cel mai mare divizor prim al numerelor de la 1 la n

Algoritmul asumă pentru început că răspunsul pentru fiecare număr în parte este chiar el însuși. După aceea, se caută divizorii primi ai fiecăruia și se modifică rezultatele. Citește aici explicațiile complete.

#include <iostream>

using namespace std;

//Ne declarăm ciurul
int ciur[1001];

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

    for(int i = 1; i <= n; i++)
        ciur[i] = i; //La început, asumăm că elementul i are cel mai mic divizor prim pe el însuși

    for(int i = 2; i <= n; i++) //Pentru toate numerele de la 2 la n
        if(ciur[i] == i) { //Elementul i este prim
            for(int j = 2 * i; j <= n; j += i) //Luăm toți multipli numărului, mai mici sau egali cu n
                ciur[j] = i;
        }

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

Indicatorul lui Euler al numerelor de la 1 la n

Indicatorul lui Euler este un algoritm foarte util, tratat în această lecție (fără ciur). Pentru explicațiile complete ale algoritmului cu ciur, poți intra pe această lecție.

#include <iostream>

using namespace std;

//Ne declarăm ciurul
int ciur[1001];

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

    for(int i = 1; i <= n; i++)
        ciur[i] = i; //La început, asumăm că numărul de numere prime cu i și mai mici ca acesta este i

    for(int i = 2; i <= n; i++)
        if(ciur[i] == i) {
            for(int j = i; j <= n; j += i)
                ciur[j] = ciur[j] / i * (i - 1);
        }

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

Alte resurse sau bibliografie

Cuprinsul lecției

Se încarcă…

Citește și

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