Como calcular totiente

Bignum Euler desenvolveu o conceito de ” totient “, ou o número de ” coprimes ” que um número tem. ” Coprimes ” são inteiros inferiores a um determinado número inteiro ” n” que partilham nenhum fator em comum com esse inteiro . Por exemplo , o número 6 tem 3 e 2 como factores . O único número menor que 6 , sem fatores comuns é 5, assim a totient de 6 seria 1 . Há uma fórmula para o cálculo do totient (mostrado pela letra grega ” phi “) para qualquer inteiro . Instruções

1

Subtrair 1 a partir do número “n ” se ” n” é primordial para obter o totient . Um número primo não compartilhará quaisquer fatores com um número menor do que isso, então todos os números menores do que será coprimes .

2

Fator o número em seus fatores primos , se o número não é primo. . , Por exemplo, 8 = 2 * 2 * 2 75 = 5 * 5 * 3

3

Ligue os fatores primos distintos nesta fórmula: .

Phi (n ) = n ( 1-1/p1 ) ( 1-1/p2 ) … ( 1-1 /p ( m)) , onde existem “m” fatores primos de “n “. Para 64 ( 2 * 2 * 2 * 2 * 2 ) , não é apenas um factor primordial distintas ( 2 ) . Assim, a fórmula funciona assim: .

Phi ( 64) = 64 ( 1-1/2 ) ou 64 ( 1/2) ou 32 Existem 32 números menos de 64 que partilham há fatores comuns com ele ( todos os números ímpares) .

phi ( 60) funciona de maneira diferente . 60 = 2 * 3 * 5, de modo que a fórmula funciona assim:

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

com todos esses fatores primos , existem apenas oito inteiros menos de 60 que não compartilham fatores comuns com ele .