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
DS
Autorul acestei lecții
Dominic Satnoianu
Această lecție a fost redactată de către Dominic Satnoianu.
© 2021 – 2025 Aspire Education Labs SRL. Toate drepturile rezervate.
Așa cum este specificat și în termeni și condiții, conținutul acestei pagini este protejat de legea drepturilor de autor și este interzisă copierea sau modificarea acestuia fără acordul scris al autorilor.
Încălcarea drepturilor de autor este o infracțiune și se pedepsește conform legii.
Comentarii 0