Escreva uma função chamada soma_divisores que recebe como parâmetro um número inteiro
e retorna a soma de todos os divisores desse número, com exceção dele próprio. Ou seja, considere o intervalo
.
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
; - retorna a soma de todos os divisores positivos de
no intervalo , ou seja, todos os divisores menores que ; - 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
. - Deve-se somar divisores no intervalo
(portanto não incluir 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
é divisor de
se existir um inteiro
tal que
. Em notação:
. Exemplo: para
, os divisores positivos são
. Como o enunciado pede apenas até
excluindo
, devemos somar
.
Passo 3
Estratégia trivial (bruta): percorrer todos os inteiros
de
até
e, para cada um, checar se
(ou seja, se
); se sim, somar
. Isso funciona e é simples, mas demora tempo proporcional a
(complexidade
). Para valores grandes de
isso pode ser lento.
Passo 4
Melhoria importante (ideia central): divisores vêm em pares. Se
e
, então existe um par
com
e
. Assim, ao testar divisores até
podemos obter também os pares maiores sem testar cada um deles separadamente. Isso reduz o número de checagens para cerca de
(complexidade
).
Passo 5
Detalhes que precisamos cuidar quando usamos pares:
- Não devemos somar
(o enunciado exclui ). Como para o par é , é preciso evitar adicionar esse par. - Se
for um quadrado perfeito, digamos , então quando o par é igual a . Nesse caso, deve-se somar apenas uma vez (não duplicar). - Devemos também tratar casos pequenos: se
o conjunto é vazio, então a soma deve ser .
Passo 6
Regras práticas para a implementação (passo a passo lógico):
- Se
, retornar . - Inicializar uma variável acumuladora
. - Percorrer
de até (inclusive). Para cada : - Se
divide (ou seja, ), então temos um par . - Acrescentar
à soma se (para isso garante que 1 será somado). - Se
(não é quadrado perfeito) e (não é o próprio ), então acrescentar .
- Se
- No final, retornar
.
Observação sobre a condição
: como
varia até
,
nunca será igual a
para
; essa verificação é mais relevante para a lógica do par
(para não somar
). No código abaixo basta verificar para
se ele é distinto de
e distinto de
.
Passo 7
Exemplos numéricos para fixar:
- Para
: -
, então testamos . -
: . Somar (não soma ). -
: . Somar e . -
: . Somar e . - Soma final
.
-
- Para
(número perfeito): - Divisores próprios:
. Soma . - O método encontra pares e evita somar
a si mesmo.
- Divisores próprios:
Passo 8
Complexidade e observações finais:
- Complexidade de tempo:
, porque só testamos até . - Complexidade de espaço:
, uso constante de memória além do input. - Tratar
devolvendo 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
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