Problema 21 - Números amigáveis

Um probleminha muito interessante! Seja d(n) a soma dos divisores próprios de um natural n. Se existirem dois números a e b tais que d(a) = b e d(b) = a, então a e b são chamados de números amigáveis. Pede-se, então, para calcular a soma de todos os números amigáveis abaixo de 10000.

O xis da quetão é, apenas, calcular a soma dos divisores de um dado número.

• O primeiro método a ser naturalmente pensado é: dado n, ir testando de 2 até raíz(n) se o candidato é divisor e, caso positivo, somar divisor e (por simetria) o resultado da divisão. Para acelerar, caso o número seja ímpar, testo a partir de 3 indo de 2 em 2. Lembrando, aí, que 1 é sempre divisor próprio e que n obviamente não o é.
• O segundo método foi usar a função divisor (ou função sigma), que como corolário provê a soma dos divisores através da decomposição de n em fatores primos. Aparentemente, um método mais inteligente... Mas, agora, vamos à realidade.

Ao invés de apenas rodar para n = 10.000 (e ter a resposta para o problema proposto), também rodei para n = 100.000 e para n = 1.000.000, a fim de comparar os dois métodos.

Código 1:

Código 2:

Desempenhos (respectivamente, método 1 e método 2), para comparação:

• n = 10.000: 1,28seg contra 9,40seg - tempo 7,3x maior
• n = 100.000: 24,30seg contra 1,77min - tempo 4,4x maior
• n = 1.000.000: 10,93min contra 18,83min - tempo 1,7x maior

Conclusão: o método mais simples, neste caso, ao contrário da (minha humilde) expectativa, é mais rápido que o método mais "elegante", embora essa diferença caia conforme aumentemos o tamanho do problema. Possivelmente, em algum momento o segundo método passe a levar vantagem. Até o momento, não resolvi pagar pra ver...