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

Ciurul lui Eratostene în C++

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. În cadrul problemelor de informatică, ciurul lui Eratostene se poate utiliza atunci când vrem să găsim numere până la 1.000.000 sau 10.000.000, altfel se poate ieși din limitele de spațiu sau de timp.

Cum funcționează algoritmul

Ciurul lui Eratostene funcționează astfel. Să presupunem că vrem să găsim toate numerele prime până la n = 50.

Vom începe prin a scrie numerele de la 2 la 50 (numărul 1 nu contează, deoarece nu este prim).

2345678
9101112131415
16171819202122
23242526272829
30313233343536
37383940414243
44454647484950

Vom lua primul număr nemarcat: adică 2. Vom spune că acesta este prim, iar pe toți multiplii săi îi vom marca, deoarece aceștia nu mai pot fi numere prime (fiind multiplu de alt număr).

2345678
9101112131415
16171819202122
23242526272829
30313233343536
37383940414243
44454647484950

Căutăm următorul număr nemarcat: 3. Vom spune iar că acesta este prim, iar pe toți multiplii săi îi vom marca. Observăm că unii dintre ei au fost deja marcați anterior, fiind și multipli de 2; acest lucru nu ne încurcă.

2345678
9101112131415
16171819202122
23242526272829
30313233343536
37383940414243
44454647484950

Căutăm următorul număr nemarcat: 5. La fel ca și anterior, vom spune că acesta este prim și vom marca multiplii săi, aceștia neputând fi numere prime.

2345678
9101112131415
16171819202122
23242526272829
30313233343536
37383940414243
44454647484950

Căutăm următorul număr nemarcat: 7. Acesta este prim și îi marcăm multiplii.

2345678
9101112131415
16171819202122
23242526272829
30313233343536
37383940414243
44454647484950

Repetăm procedeul până la final. Tabelul va arăta așa:

2345678
9101112131415
16171819202122
23242526272829
30313233343536
37383940414243
44454647484950

Iar numerele nemarcate sunt numerele prime: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.

Implementarea ciurului lui Eratostene în C++

Pentru a implementa ciurul lui Eratostene în C++, ne vom folosi de un vector, pe care îl vom numi intuitiv ciur. Lungimea vectorului trebuie să fie cel puțin egală cu numărul de numere pe care vrem să le verificăm: în exemplul anterior, am creat ciurul până la n = 50, așadar vectorul va avea minimum 50 de elemente.

Elementul ciur[i] din ciur va avea una din următoarele valori:

  • ciur[i] = 0, dacă numărul i este nemarcat (cu alte cuvinte este prim);
  • ciur[i] = 1, dacă numărul i este marcat (cu alte cuvinte nu este prim).

Inițial, toate elementele vectorului vor fi egale cu 0. Vom avansa începând de la 2 până la limita noastră n, iar când găsim un număr nemarcat (prim), îi vom marca toți multiplii săi.

La final, putem afișa pe ecran numerele nemarcate, adică cele prime. Putem de asemenea să ne întrebăm pentru orice număr dacă este sau nu prim, instant.

#include <iostream>

using namespace std;

int ciur[1001]; //Căutăm numerele prime până la 1000

int main()
{
    for(int i = 2; i <= 1000; i++) {
        if(ciur[i] == 0) { //Am găsit un număr nemarcat (prim)
            //Marcăm multiplii lui i
            for(int j = 2 * i; j <= 1000; j += i) {
                ciur[j] = 1;
            }
        }
    }

    //Afișăm pe ecran toate numerele prime găsite
    for(int i = 2; i <= 1000; i++) {
        if(ciur[i] == 0) {
            cout << "Numarul " << i << " este prim\n";
        }
    }
    return 0;
}

Alte aplicații cu ciurul lui Eratostene

Metoda prin care funcționează cirului lui Eratostene poate fi adaptat în rezolvarea altor probleme.

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

Algoritmul este foarte asemănător. 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 adună numărul i în loc să incrementeze 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] += 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 este schimbat, însă nu diferă semnificativ. 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

Codul este asemănător cu cel de dinainte. 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;
}

Exerciții propuse

Completați următoarele secvențe de cod:

Care este cel mai mare număr ce poate fi luat în considerare în ciurul de mai jos?

int v[101];
for(int i = 1; i <= ???; i++)
    if(v[i] == 0) {
        for(int j = 2 * i; j <= ???; j++)
            v[j] = 1;
    }

Să se verifice dacă numărul x este prim:

int ciur[100001];
…
if(???[x] == 0) {
    cout << x << " este prim";
} else {
    cout << x << " nu este prim";
}

Alte resurse sau bibliografie

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

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