Todos os desafios
Médio 0 resolvidos 0% de aceitação

Função Totiente de Euler

Conte os inteiros de 1 a n que não têm fator comum com n.

O que você vai aprender

  • Encontrar os fatores primos distintos de n
  • Aplicar φ(n) = n × Π(1 − 1/p) usando só inteiros
  • Tratar n = 1 e n primo

Problema

Ver original (inglês)

A função totiente de Euler, φ(n), conta os inteiros k com 1 ≤ k ≤ n e mdc(k, n) = 1. Por exemplo, φ(9) = 6, porque 1, 2, 4, 5, 7 e 8 não têm fator comum com 9.

Implemente eulers_totient(n).

Contar um k de cada vez é lento demais para n até 10^12. Use a fórmula do produto: φ(n) = n × (1 − 1/p) para cada primo distinto p que divide n. Fazendo a conta com inteiros, como n / p × (p − 1), você evita frações.

Entrada

n: um inteiro positivo.

Saída

Retorne φ(n). Pela definição, φ(1) = 1.

Restrições

1 ≤ n ≤ 10^12

Exemplos

Exemplo 1
Entrada:
n = 36

Saída esperada:
expected = 12
Entrada:
long long n = 36;

Saída esperada:
long long expected = 12;
Entrada:
long n = 36;

Saída esperada:
long expected = 12;

Explicação

36 = 2² × 3², então φ(36) = 36 × (1 − 1/2) × (1 − 1/3) = 36 × 1/2 × 2/3 = 12.

Exemplo 2
Entrada:
n = 13

Saída esperada:
expected = 12
Entrada:
long long n = 13;

Saída esperada:
long long expected = 12;
Entrada:
long n = 13;

Saída esperada:
long expected = 12;

Explicação

13 é primo, então todo k de 1 a 12 é primo com ele e φ(13) = 12.

Como abordar

Tente sozinho primeiro e depois abra uma dica de cada vez.

Dica 1

Fatore n por divisões sucessivas até √n.

Dica 2

Para cada primo distinto p, troque o resultado por resultado / p × (p − 1); divida primeiro para que o valor continue pequeno.

Dica 3

Um fator que sobra acima de 1 depois do laço também é primo.

Complexidade esperada

tempo O(√n), espaço extra O(1)

Referências

Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.