evaluar $\phi(50!)$

Question

Quiero a evaluar $\phi(50!)$ donde $\phi$ es el de Euler totient función, así que me tome la factorización en números primos de $50!$ $$2^{47}\times 3^{22}\times 5^{12}\times 7^8\times 11^4\times 13^3\times 17^2\times 19^2\times 23^2\times 29\times 31\times 37\times 41\times 43\times 47$$ entonces yo uso multiplicativity de $\phi$ y las propiedades de $\phi(p)=p-1$ $\phi(p^k)=p^{k-1}(p-1)$ por cada prime $p$ y me sale $$\phi(50!)=4218559200885839042679312107816703841788854953574400000000000000$$

Estoy pidiendo algo de la manera más inteligente para calcular los valores de $\phi$ en gran número, posiblemente no impliquen la factorización prima

Answer 1

$$\phi(50!)=50!\prod_{p\le 50\,,\,\,p\text{ a prime}}\left(1-\frac{1}{p}\right)$$

La anterior se basa en el siguiente lema:

Lema: Si

$$\Bbb N\ni n=\prod_{i=1}^kp_i^{a_i}\;\;,\;\;0<a_i\in\Bbb N\;,\;\;p_i\,\,\text{primes}$$

es el primer descomposición de $\,n\,$ , luego

$$\phi(n)=n\prod_{i=1}^k\left(1-\frac{1}{p_i}\right)$$