Problema com busca de divisores de grandes números - SOOOOCOOOORROOOO! (duvida de 5 dias)

This message was edited 9 times. Last update was at 26/04/2009 13:29:42

Problem

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

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

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

é a lógica até funciona:
ainda diminui o esforço da máquina eliminando alguns números para evitar mais divisões inuteis mais ainda é muito lento:
Teste com número de fatores menos, vai ver que funciona.

Debugger Membro desde: 02/05/2008 11:41:00 Mensagens: 66 Offline

Não entendi nada dos fors que você fez, mas se você buscar os divisores só até a raiz do número vai ficar muito mais rápido.

Nesse caso não funciona pois tenho de encontrar o número de divisores de um numero sendo eles primos ou não esse é o trabalho do método numeraDivisores() exemplo:

numeraDivisores(10) é diferente de numeraDivisores(100)

Divisores de 10 = 1,2,5,10
numeraDivisores(10)== 3 (não conto o 1)

Divisores de 100 = 1,2,5,10,20,25,50,100
numeraDivisores(100)== 9 (não conto o 1)

não tem como! O tal modo da raíz funciona quando é a divisão apenas por primos ai era fácil até podia usar o Crivo de Eratostenes.

This message was edited 1 time. Last update was at 25/04/2009 19:31:28

Viram minha observação. Pois alguem sabe como facilitar o encontro desses numeros triangulos ao invés do modo que utilizo ja no método principal.

o tempo de execeção passou de 18'59" nada de encontrar a resposta.

Debugger Membro desde: 02/05/2008 11:41:00 Mensagens: 66 Offline

O número de divisores menores que a raiz é igual ao número de divisores maiores que a raiz.

jukkinha wrote:O número de divisores menores que a raiz é igual ao número de divisores maiores que a raiz.

NÃO! veja outros:

numero de divisores:

6 = 4
36 = 9

5 = 2
25 = 3

4 = 3
16 = 5

3 = 2
9 = 3

NÃO TEM RELAÇÃO NENHUMA!!!!!!!!!!!!!!

JavaGuru Membro desde: 05/11/2006 02:51:13 Mensagens: 201 Offline

DavidUser wrote:Nesse caso não funciona pois tenho de encontrar o número de divisores de um numero sendo eles primos ou não esse é o trabalho do método numeraDivisores() exemplo:

numeraDivisores(10) é diferente de numeraDivisores(100)

Divisores de 10 = 1,2,5,10
numeraDivisores(10)== 3 (não conto o 1)

Divisores de 100 = 1,2,5,10,20,25,50,100
numeraDivisores(100)== 9 (não conto o 1)

não tem como! O tal modo da raíz funciona quando é a divisão apenas por primos ai era fácil até podia usar o Crivo de Eratostenes.

no caso de 100 4 tb eh divisor...

bom ainda nao entendi muito bem sua duvida... vc poderia dizer qual sua duvida com outras palavras???

editei o código que agora ta enchuto.
O problema é tempo que demora a encontrar o resultado,
traduzindo o problema:
era para encontrar entre os numeros da soma da seqüência natura tipo 1+2=3, 1+2+3=6, 1+2+3+4=10;
3,6,10,...

o que possui mais de 500 divisores. Ele deu o exemplo com números menores:
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
28 esse é o primeiro numero da sequência que possui 5 divisores.

agora é pra achar o com mais de 500 divisores.

teste tire o 500 e ponha 5 a resposta é 28!

Debugger Membro desde: 02/05/2008 11:41:00 Mensagens: 66 Offline

Não é pra encontrar o número de divisores da raiz... mas o número de divisores MENORES do que a raiz. -_-

6 = 1,2,3,6 - 4 divisores
36 = 1,2,3,4,6,9,12,18,36 - 8 divisores menores que a raiz

5 = 1,5 - 2 divisores
25 = 1,5,25 - 2 divisores menores que a raiz

4 = 1,2,4 - 3 divisores
16 = 1,2,4,8,16 - 4 divisores menores que a raiz

não deu pra intender oq vc disse!

acho que entendi:

36:
1,2,3,5,[6],10,15,30,36
4 4

16:
1,2,[4],8,16
2 2

funciona com todos?

GUJ Expert Membro desde: 18/02/2008 16:17:53 Mensagens: 3002 Offline

1- Procure os divisores primos menores que a raiz do número
2- Divida o número por esses divisores, e gere outra lista(conjunto) de divisores.
3- Divida esse novo conjunto pelos divisores originais, gere novos conjuntos e repita até conseguir os divisores originais.

Extra: Faça um cache desses números p/ ir mais rápido.

e quando a raiz não é inteira?

GUJ Expert Membro desde: 18/02/2008 16:17:53 Mensagens: 3002 Offline

Calcule até a parte inteira dela.

Notícias, artigos e o maior fórum brasileiro sobre Java