alguem pode me ajudar a acelerar o seguinte processo (tinha objetivo de encontrar os primos da fatoração de um número):
BigInteger x=new BigInteger("600851475143");//valor a fatorar
int z=0;
String values="";
for(BigInteger i=new BigInteger("1");i.compareTo(x)<=0;i=i.add(BigInteger.ONE)){//gera valores de 1 ao x
System.out.println(i);
if((x.remainder(i)).compareTo(BigInteger.ZERO)==0)if(primos(i)!=0)values+=i+",";//encontra divisor real, se o divisor é primo adiciona a values
}
System.out.println("valores: "+values);
}
//verifica se é primo ,se primo retorna 1 se não 0
public static int primos(BigInteger x){
int z=0,res=0;
for(BigInteger i=new BigInteger("1");i.compareTo(x)<=0;i=i.add(BigInteger.ONE))if((x.remainder(i)).compareTo(BigInteger.ZERO)==0)z++;//adiciona o numero de divisores perfeitos para x
if (z==2)res=1;//se é divisivel por apenas 2 números(é primo:1 e ele mesmo)retorna seu valor
return res;
}
O problema é que demora muito para ele testar todos os valores demoraria cerca de 3h para ele textar o último valor, e o java é conhecido por sua eficiência e velocidade me ajudem. Como acelerar o processo ou encurtar esse trabalho?
Para verificar se o fator é primo você está buscando todos os os fatores do fator, o que é desnecessário… basta que ele seja divisível por 1 número qualquer diferente dele próprio e de 1.
Além disso, na verdade nem precisa verificar se o fator é primo, basta ao encontrar um fator dividir o número pelo fator.
O código poderia ficar então assim:
BigInteger x=new BigInteger("600851475143");//valor a fatorar
String values="";
BigInteger i=new BigInteger("2")
while (x.compareTo(BigInteger.ONE)>=0) {
if((x.remainder(i)).compareTo(BigInteger.ZERO)==0) {
values+=i+",";//encontra divisor (que sempre é primo)
x = x.divide(i);
}
else {
i=i.add(BigInteger.ONE);
}
}
System.out.println("valores: "+values);
não fez diferença ele continua tendo de contar 1 a 1 oque não mudou em relação ao meu algoritimo
como o meu objetivo era achar o mairo primo, fiz o mesmo método mais inverso mais ele não executa sabe qual é o problema?
public static void main(String[]args){
BigInteger x=new BigInteger("1");//valor a fatorar
String values="";
for(BigInteger i=x;i.compareTo(BigInteger.ONE)>=0;i=i.subtract(BigInteger.ONE)){//gera valores de x ao 1 (contagem inversa)
System.out.println(i);
if((x.remainder(i)).compareTo(BigInteger.ZERO)==0)if(primos(i)!=0){
values=i.toString();
break;
}//encontra divisor real, se o divisor é primo adiciona a values
}
System.out.println("valores: "+values);
}
//verifica se é primo ,se primo retorna 1 se não 0
public static int primos(BigInteger x){
int z=0,res=0;
for(BigInteger i=new BigInteger("1");i.compareTo(x)<=0;i=i.add(BigInteger.ONE))if((x.remainder(i)).compareTo(BigInteger.ZERO)==0)z++;//adiciona o numero de divisores perfeitos para x
if (z==2)res=1;//se é divisivel por apenas 2 números(é primo:1 e ele mesmo)retorna seu valor
return res;
}
Seria mais rapido se vc gerasse uma lista de primos e não tivesse que calcular tudo a todo de novo.
Outra coisa e que vc verifica se é primo de forma alucinante: seria mais eficiente ou vc ter uma lista em memoria (http://www.math.utah.edu/~pa/math/primelist.html) ou então gerar a lista como vc faz porem comparando até a sua raiz quadrada
ou seja, se vc quer testar se X é primo, ao inves de
for(i=2;i<X;i++) if X % i == 0 return false;
isso basta
for(i=2;i<=sqrt(X);i++) if X % i == 0 return false;
Matematica:
se X = a * b, a >= raiz(X), pois,
se a e b são maiores que raiz(X), a multiplicação desses dois numeros seria maior que X.
Na verdade seu problema pode ser abordado de inumeras formas, é questão de complexidade algoritmica.
mais a raiz não é perfeita tem algum problema?
Perfeita == inteira ? Se é o caso Arredonda pra cima
pesquise pelos metodos ceil e floor
como fazer a raiz em bigInteger???