Project Euler: Problema 1
Começando com mais uma série de posts. Desta vez vou postar soluções (com explicação) de alguns problemas que resolvi no Project Euler.
Link do problema: http://projecteuler.net/problem=1
Descrição do Problema:
Se listarmos todos os números naturais menores do que 10 que são múltiplos de 3 ou 5, temos: 3, 5, 6 e 9. E a soma desses múltiplos é 23.
Encontre a soma de todos os múltiplos de 3 e 5 menores do que 1000.
Solução:
A solução que encontrei foi fazer um bloco for, de 3 até 1000, e verificar se o número é múltiplo de 3 ou 5 (usando a função mod). Caso positivo, adiciona à soma. Depois é só pegar o resultado final e fazer o input no problema.
Código:
package com.loiane.projecteuler;
public class Problem1 {
public static void main(String[] args) {
int total = 0;
//the first multiple is number 3
for (int i=3; i<1000; i++){
if ((i % 3 == 0) || (i % 5 == 0)){
total += i;
}
}
System.out.println(total);
}
}
Para ver a solução, basta executar o código acima.
Essa foi a solução mais rápida e simples que encontrei.
Mais sugestões?
Lista de mais problemas do Project Euler resolvidos: http://www.loiane.com/projetos/project-euler/
Meu repositório no GitHub: https://github.com/loiane/project-euler
Loiane,
pensei diferente, fiz dois for um de 3 em 3 e um de 5 em 5 testando se não é multiplo de 3, comparei com o que você fez, analise:
long inicio = new Date().getTime(); long total = 0;
//the first multiple is number 3 for (int i=3; i<100000000; i++){ if ((i % 3 == 0) || (i % 5 == 0)){ total += i; } }
System.out.println(total); long fim = new Date().getTime(); System.out.println(fim-inicio); inicio = new Date().getTime(); total = 0;
for (int i=3; i<100000000; i=i+3) total += i; for (int i=5; i<100000000; i+=5) if(i%3!=0) total += i; System.out.println(total); fim = new Date().getTime(); System.out.println(fim-inicio);
Olha a saída:
23333333166666688182333333316666668142
Olá!
A solução do Gustavo tem uma complexidade menor, mas acredito que a solução correta para “Encontre a soma de todos os múltiplos de 3 e 5 menores do que 1000.” seria fazer apenas um for de 3 em 3 e no if ter: i%3==0 && i%5==0, pois a soma deve ser feita com os número que são múltiplos de 3 E 5, e neste caso, bastaria percorrer de 3 em 3, caso o número seja múltiplo de 3 e também de 5, incluiria-o na soma.
Oi Loiane!
Estou praticando programação funcional, já conhece? Fiz o seu exemplo em FP com o Apache Functor
Olha como ficou.
https://gist.github.com/1320080
Curti o projeto Euler, vou dar uma olhada nos exercícios. Obrigado, Abraços!
Loiane,
pensei da mesma forma que vc, mas tb gostei da solução do gustavo.
Legal as soluções pessoal!
Essa é a parte legal de posts como esse, aprender outras formas de calcular que chegam a um mesmo resultado!
[]‘s
Opa Loiane, achei legal todas as soluções. Mas nao sei o objetivo é performace.
Porem pensei em uma solução diferente das citadas… seria …. em todas entradas verificar se o ultimo caracterer é 0 ou 5 se nao for ir somando de forma recursiva a chegar a so um caracter se for 3, 6 ou 9 pertence a soma total… Mas acredito que ocupe mais espaço e de mais trabalho p/ o processamento!!!
Bem legal esse projeto Euler. Vi hoje em seu site e escrevi sobre ele aqui:
http://www.ideiasdeprogramacao.blogspot.com/2011/12/desafios-de-programacao-project-euler.html
Minha solucao:
function solucao( razao_a, razao_b, limite)
{
var num_termos_a = ( limite – (limite % razao_a)) / razao_a;
var num_termos_b = ( limite – (limite % razao_b)) / razao_b;
var razao_ab = razao_a*razao_b;
var num_termos_ab = ( limite – (limite % razao_ab)) / razao_ab;
var soma_r3 = razao_a *num_termos_a *(num_termos_a +1)/2;
var soma_r5 = razao_b *num_termos_b *(num_termos_b +1)/2;
var soma_r15= razao_ab*num_termos_ab*(num_termos_ab+1)/2;
return (razao_a<limite?soma_r3:0) + (razao_b<limite?soma_r5:0) – (razao_ab<limite?soma_r15:0) ;
}
// numeros menores que 1000
alert(solucao(3,5,999));