Indicatorul lui Euler sau funcția lui Euler, sau totient se notează cu
Valoarea lui
Formula bazată pe descompunerea în factori
O scriere echivalentă este:
Exemplu: Pentru
Descompunerea în factori este:
Aplicând formula de mai sus obținem
Observaţie: Dacă
Teorema lui Euler:
Dacă
Secvență C++
Următoarea funcție C++ determină valoarea indicatorului lui Euler pentru o valoare n
transmisă ca parametru:
int phi(int n) { int r = n , d = 2; while(n > 1) { if(n % d == 0) { r = r / d * (d - 1); while(n % d == 0) n /= d; } d ++; if(d * d > n) d = n; } return r; }
Complexitatea ei este
Determinarea indicatorului lui Euler pe toate numerele mai mici sau egale cu n
Uneori – vezi problema #Tramvaie – trebuie să determinăm indicatorul lui Euler pentru multe numere, acestea fiind relativ mici (de exemplu, mai mici decât 1.000.000
). În această situație se poate utiliza un algoritm similar cu Ciurul lui Etatostene, bazat tot pe formula de mai sus:
Algoritmul este următorul, pentru a determina valoarea indicatorului lui Euler pentru toate numerele mai mici sau egale cu DIM
:
- declarăm un tabloul
F[]
cuDIM + 1
elemente; la final,F[x]
va reprezenta indicatorul lui Euler pentrux
- inițializăm fiecare element
F[i] = i
; scopul acestei inițializari este dublu:- pe de o parte în formula pentru indicatorul lui Euler al lui
n
produsul începe cun
; - pe de altă parte, dacă pe parcurs
F[p]
este egal cup
, deducem căp
este număr prim și va influența indicatorul lui Euler pentru toți multipli săi.
- pe de o parte în formula pentru indicatorul lui Euler al lui
- parcurgem cu
p
numerele de la2
laDIM
: - dacă
F[p]
este egal cup
, înseamnă căp
este număr prim:- decrementăm
F[p]
, aducându-l la valoarea corectă a indicatorului pentru numere prime; (A) - parcurgem toți multipli
k
ai luip
mai mari decât acesta și actualizăm valoarea lui . (B)
- decrementăm
OBS: Pașii (A) și (B) pot fi integrați într-un singur pas de tip (B). Cum?
Secvență C++
int F[DIM + 1]; for(int i =1 ; i <= DIM ; i ++) F[i] = i; for(int i = 2; i <= DIM ; i ++) if(F[i] == i) { F[i] --; for(int j =2 ; j * i <= DIM ; j ++) F[j * i]= F[j * i] / i * (i - 1); }
Probleme ataşate
Nr. | Problema | Clasa | Dificultate | Operații I/O |
---|---|---|---|---|
1 | #3289 - maxprimeintreele | 9 | medie | fișiere |
2 | #3295 - permeuler | 9 | medie | fișiere |
3 | #3227 - Tramvaie | 9 | concurs | fișiere |