Cómo calcular totient

Bignum Euler desarrolló el concepto de la " totient ", o el número de " coprimes " que un número tiene. " Coprimes " son enteros menos de un entero dado "n" que la cuota no hay factores en común con ese entero . Por ejemplo , el número 6 tiene 3 y 2 como factores . El único número inferior a 6 que no tienen factores comunes es 5 , por lo que el totient de 6 sería 1 . Existe una fórmula para calcular el totient (mostrada por la letra griega " phi" ) para cualquier entero . Instrucciones Matemáticas 1

restar 1 a la número "n" si "n " es primordial para obtener el totient . Un número primo no compartirá ningún factor con un número menor de lo que , por lo que todos los números más bajos de lo que será coprimes .
2

Factor el número en sus factores primos , si el número no es primo. . Por ejemplo , 8 = 2 * 2 * 2 75 = 5 * 5 * 3
3

Enchufe los factores primos distintos en esta fórmula : .

Phi ( n ) = n ( 1-1/p1 ) ( 1-1/p2 ) ... ( 1-1 /p ( m)) , donde hay "m" factores primos de "n ". Para 64 ( 2 * 2 * 2 * 2 * 2 ) , sólo hay un factor de primeros distintos ( 2 ) . Así que la fórmula funciona así: .

Phi ( 64 ) = 64 ( 1-1/2 ) o 64 (1 /2) o 32 Hay 32 números de menos de 64 que comparten factores comunes con ella ( todos los números impares ) .

Phi ( 60 ) funciona de manera diferente . 60 = 2 * 3 * 5 , por lo que la fórmula funciona así:

phi ( 60 ) = 60 ( 1-1/2 ) ( 1-1/3 ) ( 1-1/5 ) = 60 ( 1/2 ) ( 2/3 ) ( 4/5) = 480/60 = 8 .

con todos esos factores primos , sólo hay ocho números enteros de menos de 60 que comparten no hay factores comunes con ella .