Todos os desafios
Fácil 0 resolvidos 0% de aceitação

Soma dos divisores próprios

Some todos os divisores de n que são menores que n.

O que você vai aprender

  • Encontrar divisores aos pares
  • Parar o laço na raiz quadrada
  • Evitar contar duas vezes o divisor que é raiz quadrada

Problema

Ver original (inglês)

Os divisores próprios de n são os divisores positivos diferentes do próprio n. Para 12, eles são 1, 2, 3, 4 e 6. A soma deles (às vezes chamada de soma alíquota) indica se um número é perfeito, abundante ou deficiente. Os divisores aparecem em pares d e n / d, então basta testar valores de d até a raiz quadrada de n.

Implemente sum_of_proper_divisors(n).

Entrada

n: um inteiro positivo.

Saída

Retorne a soma de todos os divisores positivos de n que são menores que n. Para n = 1 não há nenhum, então retorne 0.

Restrições

1 ≤ n ≤ 10^12

Exemplos

Exemplo 1
Entrada:
n = 12

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

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

Saída esperada:
long expected = 16;

Explicação

1 + 2 + 3 + 4 + 6 = 16.

Exemplo 2
Entrada:
n = 28

Saída esperada:
expected = 28
Entrada:
long long n = 28;

Saída esperada:
long long expected = 28;
Entrada:
long n = 28;

Saída esperada:
long expected = 28;

Explicação

1 + 2 + 4 + 7 + 14 = 28, então 28 é um número perfeito.

Como abordar

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

Dica 1

Se d divide n, então n / d também divide n.

Dica 2

Teste d só até a raiz quadrada de n, somando os dois membros de cada par.

Dica 3

Deixe o próprio n de fora e some a raiz quadrada uma única vez quando n for um quadrado perfeito.

Complexidade esperada

tempo O(sqrt 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.