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.
Folosește următoarele shortcuturi pentru a naviga mai ușor pe platformă.
Meniu shortcuturi | ? |
Căutare probleme sau utilizatori | / |
Navigare printre rezultatele căutării | ↑, ↓ |
Meniu de contact și feedback | CTRL + Shift + F |
Ieșire din meniuri | Esc |
Setări editor | CTRL + Shift + S |
Schimbare stil editor | CTRL + Shift + E |
Șabloane de cod | CTRL + Shift + 1/2/3 |
Golire editor | CTRL + Shift + 4 |
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
.
Iată valorile lui phi(n)
, pentru 1 ≤ n ≤ 15
. Se observă că pentru un număr prim p
, phi(p) = p - 1
.
n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
φ(n) | 1 | 1 | 2 | 2 | 4 | 2 | 6 | 4 | 6 | 4 | 10 | 4 | 12 | 6 | 8 |
n
Fie p1, p2, …, pk
factorii primi ai lui n
. Atunci, phi(n)
are următoarea formulă:
Prin urmare, vom crea o variabilă phi
, inițial egală cu numărul nostru n
, după care vom găsi divizorii primi ai lui n
folosim algoritmul clasic, pe care l-am învățat în această lecție. Pentru fiecare divizor prim, vom reclacula valoarea phi
. La final, determinăm corect valoarea phi
.
Cu această observație, implementarea în C++ este:
#include <iostream>
using namespace std;
int main()
{
//Declarăm și citim n
int n;
cin >> n;
int phi = n;
for(int d = 2; d * d <= n; d++) {
if(n % d == 0) { //Am găsit un divizor prim
phi = phi / d * (d - 1);
while(n % d == 0)
n /= d;
}
}
if(n > 1) {
phi = phi / n * (n - 1);
}
cout << phi;
return 0;
}
1
la n
Vom utilza 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
.
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;
}