Problema
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
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.
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.