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