Escreva uma função chamada soma_divisores que recebe como parâmetro um número inteiro n e retorna a soma de todos os divisores desse número, com exceção dele próprio. Ou seja, considere o intervalo [1, n).
Observação 1: O nome da função deve ser exatamente como especificado acima e seu arquivo deve obrigatoriamente se chamar problema10.py.
Observação 2: Seu programa deve conter apenas a função descrita acima. Você não precisa realizar a entrada e saída de dados (não precisa usar as funções input() e print()).

Passo 1

O enunciado pede que eu escreva uma função chamada soma_divisores que:
  • recebe um parâmetro inteiro n;
  • retorna a soma de todos os divisores positivos de n no intervalo [1,n), ou seja, todos os divisores menores que n;
  • não deve haver entrada ou saída no programa (não usar input() ou print());
  • o arquivo deve se chamar problema10.py e conter apenas a função (isso significa que a função deve ter exatamente o nome pedido).
Informações relevantes dadas:
  • O parâmetro é um número inteiro n.
  • Deve-se somar divisores no intervalo [1,n) (portanto não incluir n na soma).
  • O resultado a retornar é um único inteiro (a soma).
  • Não há necessidade de tratar entrada/saída no arquivo.

Passo 2

O que é um divisor? Um número inteiro positivo d é divisor de n se existir um inteiro k tal que n = d\cdot k. Em notação: d\mid n. Exemplo: para n=12, os divisores positivos são 1,2,3,4,6,12. Como o enunciado pede apenas até n excluindo n, devemos somar 1+2+3+4+6 = 16.

Passo 3

Estratégia trivial (bruta): percorrer todos os inteiros d de 1 até n-1 e, para cada um, checar se d\mid n (ou seja, se n\%d==0); se sim, somar d. Isso funciona e é simples, mas demora tempo proporcional a n (complexidade O(n)). Para valores grandes de n isso pode ser lento.

Passo 4

Melhoria importante (ideia central): divisores vêm em pares. Se d\mid n e d \le \sqrt{n}, então existe um par e = n/d com e \ge \sqrt{n} e e\mid n. Assim, ao testar divisores até \lfloor\sqrt{n}\rfloor podemos obter também os pares maiores sem testar cada um deles separadamente. Isso reduz o número de checagens para cerca de \sqrt{n} (complexidade O(\sqrt{n})).

Passo 5

Detalhes que precisamos cuidar quando usamos pares:
  • Não devemos somar n (o enunciado exclui n). Como para d=1 o par é n, é preciso evitar adicionar esse par.
  • Se n for um quadrado perfeito, digamos n = m^2, então quando d=m o par e é igual a d. Nesse caso, deve-se somar apenas uma vez d (não duplicar).
  • Devemos também tratar casos pequenos: se n \le 1 o conjunto [1,n) é vazio, então a soma deve ser 0.

Passo 6

Regras práticas para a implementação (passo a passo lógico):
  1. Se n \le 1, retornar 0.
  2. Inicializar uma variável acumuladora s = 0.
  3. Percorrer d de 1 até \lfloor\sqrt{n}\rfloor (inclusive). Para cada d:
    • Se d divide n (ou seja, n \bmod d = 0), então temos um par e = n // d.
    • Acrescentar d à soma se d \neq n (para d=1 isso garante que 1 será somado).
    • Se e \neq d (não é quadrado perfeito) e e \neq n (não é o próprio n), então acrescentar e.
  4. No final, retornar s.
Observação sobre a condição d \neq n: como d varia até \sqrt{n}, d nunca será igual a n para n>1; essa verificação é mais relevante para a lógica do par e (para não somar n). No código abaixo basta verificar para e se ele é distinto de d e distinto de n.

Passo 7

Exemplos numéricos para fixar:
  • Para n=12:
    • \sqrt{12}\approx 3{,}46, então testamos d=1,2,3.
    • d=1: e=12. Somar 1 (não soma 12).
    • d=2: e=6. Somar 2 e 6.
    • d=3: e=4. Somar 3 e 4.
    • Soma final 1+2+6+3+4 = 16.
  • Para n=28 (número perfeito):
    • Divisores próprios: 1,2,4,7,14. Soma 28.
    • O método encontra pares e evita somar 28 a si mesmo.

Passo 8

Complexidade e observações finais:
  • Complexidade de tempo: O(\sqrt{n}), porque só testamos d até \sqrt{n}.
  • Complexidade de espaço: O(1), uso constante de memória além do input.
  • Tratar n \le 1 devolvendo 0 evita problemas com intervalos vazios.

Resposta

def soma_divisores(n):
if n <= 1:
return 0
s = 0
d = 1
while d * d <= n:
if n % d == 0:
e = n // d
if d != n:
s += d
if e != d and e != n:
s += e
d += 1
return s

Exercícios relacionados