Project Euler Solutions2017–Presente

Em andamento

O site ProjectEuler.net reúne uma série de problemas matemáticos que requerem programação para serem resolvidos. Desde 2017 venho resolvendo os problemas em ordem cronológica. As soluções a partir do problema 15 estão disponíveis no repositório Project Euler Solutions.

Exemplos

Problema 10 — Soma de Primos
A soma dos números primos menores que 10 é 2 + 3 + 5 + 7 = 17.
Encontre a soma de todos os primos menores que 2.000.000.

O desafio desse problema é bolar um jeito de calcular números primos grandes. A abordagem ingênua de checar cada número individualmente por seus divisores é inviável, porque é ineficiente e demandaria tempo de processamento demais.

Para resolver o problema, implementei o algoritmo do Crivo de Erastótenes, que é uma abordagem simples e eficiente o suficiente para este problema.

Problema 12 — Número triangular altamente divisível
A sequência de números triangulares é gerada pela soma dos números naturais. Logo, o 7º número triangular seria 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. Os primeiros dez termos seriam:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

28 é o primeiro número triangular a ter mais de 5 divisores (1, 2, 3, 7, 14 e 28). Qual é o primeiro número triangular a ter mais de quinhentos divisores?

O problema 12 pode ser dividido em 2 tarefas diferentes: calcular números triangulares e contar os divisores. As duas tarefas podem ser otimizadas.

Calcular os números triangulares não é uma tarefa difícil, mas levando em conta a quantidade de números que serão computados, as coisas começam a se complicar. Uma maneira mais elegante de encontrar o enésimo número triangular é usando a fórmula n(n+1)/2.

Encontrar os divisores de um número também não deveria ser uma tarefa muito difícil, mas testar todos os números começa a ficar muito ineficiente muito rápido. É possível calcular os divisores de um número usando a sua forma fatorada e análise combinatória

Resumidamente, a quantidade de divisores de um número é o total de todos os arranjos possíveis entre seus fatores primos. Uma explicação mais detalhada desse método pode ser encontrada nesse artigo em gmathacks.com.