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!!!
[quote=DavidUser]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.[/quote]
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!
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?
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?
Calcule até a parte inteira dela.
fiz o seguinte:
int z=0,num=35,tam1=0;
String div=" ";
for(int i=1;i<=num;i++){
if(num%i==0 & i==Math.sqrt(num))tam1=div.length()/2;
if(num%i==0){
z++;
div+=i+" ";
}
}mas quando a raiz não é exata como ele pode calcular o tamanho?
a minha idéia era pegar o mais proximo=
35:
1,5,7,35
raiz de 35=5.9
então o mais proximo é 5
1,[5],7,35
1 2
3 divisores(fora o 1);
funciona mais não sei como fazer isso em código ja pensei em array mais ai não tem como definir o tamanho, tem como fazer om list?
como usa o list?
ja tentei incluir em string mais não da pra usar quebrando em splint.
COMO EU FAÇO PRA FACILITAR O Método quando o valor da raiz não é inteiro???
Raiz do número? não, não, o número já é a raiz. Desculpe se me confundi.
Para saber se um número é primo, é preciso calcular somente até a raiz dele.
Bem, sobre o algorítimo, tem um um que precisa encontrar os numeros e ir dividindo, é mais fácil de entender que o outro:
[code] private List fatoresPrimos(long num)
{
ArrayList lista = new ArrayList();
long fator = 2;
while (fator * fator <= num)
{
if (num % fator == 0) // se o numero é divisivel pelo suposto fator
{
lista.add(fator); // então ele é um fator
num = num / fator; // um fator foi encontrado, diminui o numero
}
else // não é um fator, continua procurando
{
fator++;
}
}
if (num != 1) // sobrou algum fator?
{
lista.add(num); // o adiciona
}
return lista;
}[/code]Este foi chato de achar:
268028766720 -> [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 15, 16, 18, 20, 22, 23, 24, 26, 27, 30, 32, 33, 36, 39, 40, 44, 45, 46, 48, 52, 54, 55, 60, 64, 65, 66, 69, 72, 78, 80, 81, 88, 90, 92, 96, 99, 104, 108, 115, 117, 120, 128, 131, 132, 135, 138, 143, 144, 156, 160, 162, 165, 176, 180, 184, 192, 195, 198, 207, 208, 216, 234, 240, 243, 253, 256, 262, 264, 270, 276, 288, 297, 299, 312, 320, 324, 345, 351, 352, 360, 368, 384, 393, 396, 405, 414, 416, 432, 468, 480, 486, 495, 512, 524, 528, 540, 552, 576, 585, 594, 621, 624, 640, 648, 655, 702, 704, 715, 720, 736, 768, 786, 792, 810, 828, 832, 864, 891, 936, 960, 972, 1035, 1048, 1053, 1056, 1080, 1104, 1152, 1179, 1188, 1215, 1242, 1248, 1265, 1280, 1296, 1404, 1408, 1440, 1441, 1472, 1485, 1536, 1572, 1584, 1620, 1656, 1664, 1703, 1728, 1755, 1782, 1863, 1872, 1920, 1944, 1965, 2096, 2106, 2112, 2145, 2160, 2208, 2304, 2358, 2376, 2430, 2484, 2496, 2560, 2592, 2673, 2808, 2816, 2880, 2944, 3013, 3105, 3144, 3159, 3168, 3240, 3289, 3312, 3328, 3456, 3537, 3564, 3726, 3744, 3795, 3840, 3888, 4192, 4212, 4224, 4320, 4416, 4455, 4608, 4716, 4752, 4860, 4968, 4992, 5184, 5265, 5346, 5589, 5616, 5632, 5760, 5888, 5895, 6288, 6318, 6336, 6435, 6480, 6624, 6656, 6912, 7074, 7128, 7205, 7452, 7488, 7680, 7776, 8384, 8424, 8448, 8640, 8832, 9315, 9432, 9504, 9720, 9936, 9984, 10368, 10611, 10692, 11178, 11232, 11385, 11520, 11776, 12576, 12636, 12672, 12960, 13248, 13365, 13824, 14148, 14256, 14904, 14976, 15552, 15795, 16445, 16768, 16848, 16896, 17280, 17664, 17685, 18733, 18864, 19008, 19305, 19440, 19872, 19968, 20736, 21222, 21384, 21615, 22356, 22464, 23040, 25152, 25272, 25344, 25920, 26496, 26730, 27945, 28296, 28512, 29808, 29952, 31104, 31590, 31833, 33536, 33696, 34155, 34560, 35328, 37728, 38016, 38880, 39169, 39744, 41472, 42444, 42768, 44712, 44928, 49335, 50304, 50544, 50688, 51840, 52992, 53055, 53460, 55890, 56592, 57024, 57915, 59616, 59904, 62208, 63180, 63666, 64845, 67072, 67392, 69120, 75456, 76032, 77760, 79488, 84888, 85536, 89424, 89856, 93665, 100608, 101088, 102465, 103680, 105984, 106920, 111780, 113184, 114048, 119232, 124416, 126360, 127332, 134784, 148005, 150912, 152064, 155520, 158976, 159165, 169776, 171072, 173745, 178848, 179712, 194535, 201216, 202176, 207360, 213840, 223560, 226368, 228096, 238464, 252720, 254664, 269568, 280995, 301824, 307395, 311040, 317952, 318330, 339552, 342144, 347490, 357696, 404352, 427680, 430859, 444015, 447120, 452736, 456192, 476928, 505440, 509328, 539136, 583605, 603648, 614790, 622080, 636660, 679104, 684288, 694980, 715392, 808704, 842985, 855360, 894240, 905472, 953856, 1010880, 1018656, 1229580, 1273320, 1332045, 1358208, 1368576, 1389960, 1430784, 1617408, 1710720, 1750815, 1788480, 1810944, 2021760, 2037312, 2154295, 2459160, 2528955, 2546640, 2716416, 2779920, 2861568, 3421440, 3501630, 3576960, 3996135, 4043520, 4074624, 4918320, 5093280, 5432832, 5559840, 6462885, 6842880, 7003260, 7153920, 7586865, 7992270, 8087040, 8149248, 9836640, 10186560, 11119680, 14006520, 14307840, 15984540, 16298496, 19388655, 19673280, 20373120, 22239360, 22760595, 28013040, 31969080, 39346560, 40746240, 44478720, 45521190, 56026080, 58165965, 63938160, 78693120, 81492480, 88957440, 91042380, 112052160, 127876320, 157386240, 174497895, 182084760, 224104320, 255752640, 364169520, 448208640, 511505280, 523493685, 728339040, 896417280, 1023010560, 1046987370, 1456678080, 2046021120, 2093974740, 2913356160, 4187949480, 5826712320, 8375898960, 11653424640, 16751797920, 33503595840, 67007191680, 134014383360, 268028766720] : size 520
BUILD SUCCESSFUL (total time: 4 minutes 4 seconds)
package fatorar;
import java.util.ArrayList;
import java.util.List;
import java.util.SortedSet;
import java.util.TreeSet;
import javax.swing.JOptionPane;
public class Fatorizador2
{
public static void main(String[] args)
{
String s = JOptionPane.showInputDialog("Número de fatores a encontrar:");
long limite = Long.parseLong(s);
Gerador gerador = new Gerador();
long n = 0;
List<Long> lista;
SortedSet<Long> set;
do
{
n = gerador.prox();
lista = fatoresPrimos(n);
set = combinar(lista, new TreeSet<Long>(), n);
}
while (set.size() <= limite);
System.out.printf("%d -> %s : size %d\n", n, set, set.size());
}
private static List<Long> fatoresPrimos(long num)
{
if (num < 0)
throw new IllegalArgumentException("Pare!");
ArrayList<Long> lista = new ArrayList<Long>();
lista.add(1L);
long fator = 2;
while (fator * fator <= num)
{
if (num % fator == 0) // se o numero é divisivel pelo suposto fator
{
lista.add(fator); // então ele é um fator
num = num / fator; // um fator foi encontrado, diminui o numero
}
else // não é um fator, continua procurando
{
fator++;
}
}
if (num != 1) // sobrou algum fator?
{
lista.add(num); // o adiciona
}
return lista;
}
/**
* Multiplicação do combinatorio de todos os fatores primos
* retorna todos os divisores de n.
*/
private static SortedSet<Long> combinar(List<Long> lista, SortedSet<Long> resultado_anterior, long n)
{
// A idéia é gerar vários triangulos como o de Pascal, porém com multiplicações
// são gerados triangulos a partir da lista, e a partir do próprio resultados dessas multiplicações
// recursivamente
if (lista.isEmpty())
return resultado_anterior;
long a = lista.get(0);
List<Long> tail = new ArrayList<Long>(lista);
tail.remove(0);
TreeSet<Long> resultado = new TreeSet<Long>();
resultado.add(a);
for (Long b : tail)
{
long multi = a * b;
if (n % multi == 0)
resultado.add(multi);
}
for (Long b : resultado_anterior)
{
long multi = a * b;
if (n % multi == 0)
resultado.add(multi);
}
resultado.addAll(combinar(tail, resultado, n));
return resultado;
}
}
class Gerador
{
int n = 0;
long soma = 0;
public long prox()
{
n++;
soma = soma + n;
return soma;
}
}Bem, opps de novo, o anterior tá um pouco bugado, este parece ser o de verdade:
76576500 -> [1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 18, 20, 21, 22, 25, 26, 28, 30, 33, 34, 35, 36, 39, 42, 44, 45, 50, 51, 52, 55, 60, 63, 65, 66, 68, 70, 75, 77, 78, 84, 85, 90, 91, 99, 100, 102, 105, 110, 117, 119, 125, 126, 130, 132, 140, 143, 150, 153, 154, 156, 165, 170, 175, 180, 182, 187, 195, 198, 204, 210, 220, 221, 225, 231, 234, 238, 250, 252, 255, 260, 273, 275, 286, 300, 306, 308, 315, 325, 330, 340, 350, 357, 364, 374, 375, 385, 390, 396, 420, 425, 429, 442, 450, 455, 462, 468, 476, 495, 500, 510, 525, 546, 550, 561, 572, 585, 595, 612, 630, 650, 660, 663, 693, 700, 714, 715, 748, 750, 765, 770, 780, 819, 825, 850, 858, 875, 884, 900, 910, 924, 935, 975, 990, 1001, 1020, 1050, 1071, 1092, 1100, 1105, 1122, 1125, 1155, 1170, 1190, 1260, 1275, 1287, 1300, 1309, 1326, 1365, 1375, 1386, 1428, 1430, 1500, 1530, 1540, 1547, 1575, 1625, 1638, 1650, 1683, 1700, 1716, 1750, 1785, 1820, 1870, 1925, 1950, 1980, 1989, 2002, 2100, 2125, 2142, 2145, 2210, 2244, 2250, 2275, 2310, 2340, 2380, 2431, 2475, 2550, 2574, 2618, 2625, 2652, 2730, 2750, 2772, 2805, 2860, 2925, 2975, 3003, 3060, 3094, 3150, 3250, 3276, 3300, 3315, 3366, 3465, 3500, 3570, 3575, 3740, 3825, 3850, 3900, 3927, 3978, 4004, 4095, 4125, 4250, 4284, 4290, 4420, 4500, 4550, 4620, 4641, 4675, 4862, 4875, 4950, 5005, 5100, 5148, 5236, 5250, 5355, 5460, 5500, 5525, 5610, 5775, 5850, 5950, 6006, 6188, 6300, 6375, 6435, 6500, 6545, 6630, 6732, 6825, 6930, 7140, 7150, 7293, 7650, 7700, 7735, 7854, 7875, 7956, 8190, 8250, 8415, 8500, 8580, 8925, 9009, 9100, 9282, 9350, 9625, 9724, 9750, 9900, 9945, 10010, 10500, 10710, 10725, 11050, 11220, 11375, 11550, 11700, 11781, 11900, 12012, 12155, 12375, 12750, 12870, 13090, 13260, 13650, 13860, 13923, 14025, 14300, 14586, 14625, 14875, 15015, 15300, 15470, 15708, 15750, 16380, 16500, 16575, 16830, 17017, 17325, 17850, 17875, 18018, 18564, 18700, 19125, 19250, 19500, 19635, 19890, 20020, 20475, 21420, 21450, 21879, 22100, 22750, 23100, 23205, 23375, 23562, 24310, 24750, 25025, 25500, 25740, 26180, 26775, 27300, 27625, 27846, 28050, 28875, 29172, 29250, 29750, 30030, 30940, 31500, 32175, 32725, 33150, 33660, 34034, 34125, 34650, 35700, 35750, 36036, 36465, 38250, 38500, 38675, 39270, 39780, 40950, 42075, 42900, 43758, 44625, 45045, 45500, 46410, 46750, 47124, 48620, 49500, 49725, 50050, 51051, 53550, 53625, 55250, 55692, 56100, 57750, 58500, 58905, 59500, 60060, 60775, 64350, 65450, 66300, 68068, 68250, 69300, 69615, 70125, 71500, 72930, 75075, 76500, 77350, 78540, 81900, 82875, 84150, 85085, 86625, 87516, 89250, 90090, 92820, 93500, 98175, 99450, 100100, 102102, 102375, 107100, 107250, 109395, 110500, 115500, 116025, 117810, 121550, 125125, 128700, 130900, 133875, 136500, 139230, 140250, 145860, 150150, 153153, 154700, 160875, 163625, 165750, 168300, 170170, 173250, 178500, 180180, 182325, 193375, 196350, 198900, 204204, 204750, 210375, 214500, 218790, 225225, 232050, 235620, 243100, 248625, 250250, 255255, 267750, 278460, 280500, 294525, 300300, 303875, 306306, 321750, 327250, 331500, 340340, 346500, 348075, 364650, 375375, 386750, 392700, 409500, 420750, 425425, 437580, 450450, 464100, 490875, 497250, 500500, 510510, 535500, 546975, 580125, 589050, 607750, 612612, 643500, 654500, 696150, 729300, 750750, 765765, 773500, 841500, 850850, 900900, 911625, 981750, 994500, 1021020, 1093950, 1126125, 1160250, 1178100, 1215500, 1276275, 1392300, 1472625, 1501500, 1531530, 1701700, 1740375, 1823250, 1963500, 2127125, 2187900, 2252250, 2320500, 2552550, 2734875, 2945250, 3063060, 3480750, 3646500, 3828825, 4254250, 4504500, 5105100, 5469750, 5890500, 6381375, 6961500, 7657650, 8508500, 10939500, 12762750, 15315300, 19144125, 25525500, 38288250, 76576500] : size 576
BUILD SUCCESSFUL (total time: 3 seconds)
package fatorar;
import java.util.SortedSet;
import java.util.TreeSet;
import javax.swing.JOptionPane;
public class Fatorizador3
{
public static void main(String[] args)
{
String s = JOptionPane.showInputDialog("Número de fatores a encontrar:");
long limite = Long.parseLong(s);
Gerador gerador = new Gerador();
long n = 0;
SortedSet<Long> set;
do
{
n = gerador.prox();
set = fatores(n);
}
while (set.size() <= limite);
System.out.printf("%d -> %s : size %d\n", n, set, set.size());
for (Long long1 : set)
{
if (n % long1 != 0)
System.out.println("Erro!");
}
}
private static SortedSet<Long> fatores(long num)
{
if (num < 0)
throw new IllegalArgumentException("Pare!");
SortedSet<Long> set = new TreeSet<Long>();
SortedSet<Long> resultado = new TreeSet<Long>();
long fator = 2;
while (fator * fator <= num)
{
if (num % fator == 0) // se o numero é divisivel pelo suposto fator
{
resultado.add(num);
for (Long divisor : resultado)
{
set.add(divisor / fator);
}
resultado.addAll(set);
num = num / fator; // um fator foi encontrado, diminui o numero
}
else // não é um fator, continua procurando
{
fator++;
}
}
if (num > 1)
{
for (Long divisor : resultado)
{
set.add(divisor / num);
}
resultado.addAll(set);
}
return resultado;
}
}Decidi fazer como fazíamos na escola na aula de matemática. Ao mesmo tempo que divido o numero principal, também divido os subfatores encontrados no meio do caminho. Esse tá certo.
É tão rápido comparado ao anterior que até resolvi checar se tava certo mesmo.
Ótimo!
Bom mesmo, mas sou iniciante no java e não tinha conhecimento desses recursos vc pode me explicar como funciona alguns como o sistema de criação de listas, do, trown, á ja li muito sobre herança mais ainda não entendi bem.
Simplificando: Me esplica o seu codigo e os recursos que usou,
Muito Obrigado!
Bem, sobre como funcionam listas, conjuntos, do, exceções, te indico a melhor fonte para aprender:
Baixe as apostilas CS-14 e FJ-11.
Sobre como o algorítmo funciona, lembra dos tempos que aprendemos a calcular o máximo divisor comum e o minimo multiplo comum entre vários números, montando uma tabela e dividindo os números por um mesmo fator?
O que acontece é que vou dividindo um só número, e guardo ele e o resultado dessa divisão para dividir na próxima etapa, e repito isso até acabar.
Exemplo:
---------| ACUMULADO
2| 120 -> 120
// 2| 60
2| 60 -> 120 60
// 2| 60 30
2| 30 -> 120 60 30
// 2| 60 30 15
3| 15 -> 120 60 30 15
// 3| 40 20 10 5
5| 5 -> 120 60 40 30 20 15 10 5
// 5| 24 12 8 6 4 3 2 1
FATORES = 120 60 40 30 24 20 15 12 10 8 6 5 4 3 2 1
Espero que dê para entender.
Aee legal entendi!
Na teoria do minimo múltiplo comum eles descreviam que esses eram os divisores do número?
de quem foi essa observação? onde o resultado do divisor comum é um divisor.
Vlw msm.
esse é o problema 12 do Project Euler.
http://projecteuler.net/index.php?section=problems&id=12
Há uma boa discussão sobre ele aqui: http://www.guj.com.br/posts/list/119394.java