Indicatorul lui Euler 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 indicatorii lui Euler
ale tuturor numerelor de la 1
la n
.
Exemplu. Pentru n = 10
, indicatorii sunt 1, 1, 2, 2, 4, 2, 6, 4, 6, 4
(1
are indicatorul 1
, 2
are indicatorul 1
, 3
are indicatorul 2
,
etc.).
Ce este indicatorul lui Euler
Indicatorul lui Euler al unui număr n
, notat cu φ(n)
sau phi(n)
,
reprezintă numărul de numere mai mici sau egale cu n
și totodată prime cu
acesta. Spre exemplu, phi(4) = 2
, deoarece singurele numere mai mici sau
egale cu 4
și prime cu acesta sunt 1
și 3
.
Vom prezenta o metodă ce se bazează pe algoritmul ciurului lui Eratostene.
Cum se determină indicatorii lui Euler pentru numerele de la 1
la n
Vom utiliza un algoritm similar cu cel al ciurului 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.
Puteți citi mai multe despre acest algoritm (și să urmăriți implementarea) pe
această pagină.
Algoritmul de mai jos se folosește de formula matematică a lui phi(n)
. Dacă
știm factorii primi ai unui număr, atunci avem formula:
Unde p1, p2, …, pk
sunt factorii primi ai lui n
.
Prin urmare, vom salva în ciur
valoarea n
, iar de fiecare dată când
întâlnim o valoare primă i
, vom luat toți multiplii j
ai săi, astfel încât
i
este un factor prim al lui j
. Vom înmulți phi(j)
cu (i - 1) / i
.
Implementare C++
Iată codul care implementează ideea de mai sus:
#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