Velocidade de execução - Ajuda

No seu caso, o problema da fatoração é que você está usando um algoritmo inadequado.

A primeira coisa que você deve entender é que fatoração é um problema razoavelmente difícil. E é por isso que é usado em alguns algoritmos de criptografia famosos, como o RSA.

Para não usar métodos de fatoração muito complicados (procure por “prime factorization algorithms” no Google e vai entender o que estou falando), vou propor um método um pouco lento mas que deve funcionar no seu caso.

A primeira coisa a fazer é preparar uma tabela de números primos que vá até o valor da raiz quadrada desse seu número (por exemplo, se o número é 600851475143, então você tem de preparar uma tabela que vá até 775146. Para fazer uma tabela dessas, use o algoritmo “Crivo de Eratóstenes” (Erathostenes’s Sieve; você pode encontrá-lo facilmente na Internet). Você pode usar, para economizar um pouco de espaço, um java.util.BitSet para representar essa tabela de primos. Acho que um programa bem simples consegue determinar essa tabela de primos em cerca de 5 segundos de CPU, o que é aceitável.

Determinar se um número é primo do jeito que você está fazendo vai demorar demais, e não é isso que você quer.

A seguir, faça do jeito que você estava fazendo (ficar fazendo divisão repetida por um determinado primo, e passar para o próximo, até que você fique com o número 1).

E a propósito, para esse número que você passou ( 600851475143 ), você pode usar um long mesmo, não precisa de um BigInteger, que só vai atrasar sua vida. Números um pouco maiores que esse (nem passam do tamanho de um long) já são bem difíceis de fatorar, e nesse caso você teria de usar algum método poderoso de fatoração.

ja tentei com long mais não adiantou

infelizmente esse computador é um celeron 560 do meu irmão,
no caso com um core 2Duo quanto almentaria na velocidade em 2x,3x,4x?
vc sabe?

Você perguntou se “aumentaria” ou se “alimentaria”?
De qualquer maneira, você não pode usar esse seu método para determinar se um número é primo, porque é o lugar onde você gasta mais tempo.
Você vai ter de criar a tal tabela de números primos com o crivo de Eratóstenes.
Você não vai escapar disso, porque você pode rodar seu programa, sem alterações, em um Core i7 (o mais rápido processador da Intel) que ainda vai demorar séculos para rodar.

sei que terei de fazer o metodo de crivo.
Mas a nível de informação sabe qual o processador mais potente que uma placa de notebook suporta hj?
Vou montar um notebook, estou buscando um configuração bem incrementada pois cursarei a facudade de engenharia da computação e pretendo projetar softwares de grande magnitude.

Tá bom, aqui vai uma implementação do Crivo de Eratóstenes. Ele não está otimizado, mas roda em alguns segundos.

import java.util.*;
class Sieve {
    private BitSet bs;
    public void findPrimes (int n) {
        bs = new BitSet (n+1);
        int sq = (int) Math.sqrt (n);
        // Ao final desta rotina, todos os bits marcados serão primos, e os
        // bits desmarcados serão números compostos.
        bs.set (0, n, true); // marcando todos os bits como primos...
        // Agora vamos achar o primeiro bit primo, e desmarcar todos os bits 
        // que são múltiplos dele. Vamos começar por 3
        int x = 2;
        while (x <= sq) {
            for (int i = x + x; i <= n; i += x) { 
                bs.clear (i);
            }
            // Devemos achar o próximo bit setado que seja maior que x
            x = bs.nextSetBit (x + 1);
        }
    }
    public boolean isPrime (int n) {
        return bs.get (n);
    }
    public static void main(String[] args) {
        Sieve s = new Sieve();
        s.findPrimes (775146);
        for (int i = 1; i <= 100; ++i) {
            System.out.println (i + " is " + (s.isPrime(i) ? "prime" : "not prime"));
        }
    }
}

DavidUser:

sei que terei de fazer o metodo de crivo.
Mas a nível de informação sabe qual o processador mais potente que uma placa de notebook suporta hj?
Vou montar um notebook, estou buscando um configuração bem incrementada pois cursarei a faculdade de engenharia da computação e pretendo projetar softwares de grande magnitude.

Hum… dê uma olhada no site da Intel e veja quais são os processadores “mobile”.

sinceramente não encontrei o tal método pronto.Vc não o possui?

Dê um refresh na sua página. Eu o postei faz pouco tempo.

ele só encontrou os primos de 1 a 100!!!

Eu só imprimi os primos de 1 a 100, para eu poder conferir (não queria postar um programa errado).
O resto dos primos está calculado, puxa vida!

Poste depois se o tal número ( 600851475143 ) pode ser fatorado ou se é primo.

no problema q estou resolvendo tenho que encontrar o maior numero primo que divide esse valor ou seja ele não é primo!
era isso q queria dizer, meu programa busca os primos que dividem um número sem repetir nenhum.
mas a idéia da raiz parece boa!

Só para você conferir, a fatoração desse número dá:

71^1 . 839^1 . 1471^1 . 6857^1

Experimente o seu algoritmo com o número 600851475147. A fatoração vai dar

3^1 . 7^2 . 11^1 . 163^1 . 2279657^1

como é q é?! Voutei agora to vuando

Demorou quanto tempo pra encontrar?

Fatoração é um código complicado muito custo computacional... o ideal é usar Crivo de Eratóstenes... :D

Voce escreve todos os numeros no intervalo [1 - x ] e risca os numeros não primos a partir dos numeros primos.

Vou fazer o algorimo q vc pediu esse fds...

import java.math.BigInteger;

    public class Main {
       public static void main(String[]args){

           BigInteger x=new BigInteger("600851475143");

           System.out.println("O numero " + x.floatValue() + " e primo?\n"+ (isPrimo(x) == true ? "sim":"não"));

       }
       
       public static boolean isPrimo(BigInteger x){

           for(BigInteger c = BigInteger.ONE; c.compareTo(x) == -1 ; c = c.add(BigInteger.ONE) ){
                if ((x.remainder(c).compareTo(BigInteger.ZERO) != 0) || (c.compareTo(BigInteger.ONE) == 0) ){
                } else {
                    return false;
                }
           }
           return true;
       }
    }

Se tiver errado e pq to com sono, depois eu mando o do crivo... :wink:

Se alguém quiser um código eficiente para saber se um numero é primo ou não.

public static boolean isPrime(long num) {
		if (num > 1)
			if ((num % 2) != 0 || (num == 2))
				if ((num % 3 != 0) || (num == 3))
					if ((num % 5) != 0 || (num == 5))
						if ((num % 7) != 0 || (num == 7))
							return true;
		return false;
	}

Sim e funciona… podem testar em um loop de 0 a quanto voce quiser.

E pode ser facilmente convertido para usar BigInteger.

Mark_Ameba:

Se alguém quiser um código eficiente para saber se um numero é primo ou não.

public static boolean isPrime(long num) {
		if (num > 1)
			if ((num % 2) != 0 || (num == 2))
				if ((num % 3 != 0) || (num == 3))
					if ((num % 5) != 0 || (num == 5))
						if ((num % 7) != 0 || (num == 7))
							return true;
		return false;
	}

Sim e funciona… podem testar em um loop de 0 a quanto voce quiser.

E pode ser facilmente convertido para usar BigInteger.

Isso é primeiro de abril, não? Se num == 121, por exemplo, seu método retorna “true”. Nem precisei rodar o programa; só de olhar seu programa já vi que ele testa se seu número é múltiplo de 2, 3, 5, ou 7. O próximo primo é 11, então esse método dá pau com 11 vezes 11, que é um número composto.

thingol:

Isso é primeiro de abril, não? Se num == 121, por exemplo, seu método retorna “true”. Nem precisei rodar o programa; só de olhar seu programa já vi que ele testa se seu número é múltiplo de 2, 3, 5, ou 7. O próximo primo é 11, então esse método dá pau com 11 vezes 11, que é um número composto.

Esse método é de um amigo meu que me mandou… quando testei parecia correto.

Agora vi que realmente não esta.

sem comentários… acho que meu método iterativo lento e melhor que esse… :lol:

mas até que esse metodo tem 1 boa idéia, o que eu acho q ele quis dizer Sim e "funciona… podem testar em um loop de 0 a quanto voce quiser. " é que a comparação sempre se repete if ((num % x) != 0 || (num == x)) sendo n numero primo.

As comparações vão até não haverem primos menores que o numero verificado.

Com isso da pra pensar numa maneira de expandi a arvore de decisão…

certo?

Mark_Ameba:

Se alguém quiser um código eficiente para saber se um numero é primo ou não.

public static boolean isPrime(long num) {
		if (num > 1)
			if ((num % 2) != 0 || (num == 2))
				if ((num % 3 != 0) || (num == 3))
					if ((num % 5) != 0 || (num == 5))
						if ((num % 7) != 0 || (num == 7))
							return true;
		return false;
	}

Sim e funciona… podem testar em um loop de 0 a quanto voce quiser.

E pode ser facilmente convertido para usar BigInteger.

wallacetepes:

sem comentários… acho que meu método iterativo lento e melhor que esse… :lol:

mas até que esse metodo tem 1 boa idéia, o que eu acho q ele quis dizer Sim e "funciona… podem testar em um loop de 0 a quanto voce quiser. " é que a comparação sempre se repete if ((num % x) != 0 || (num == x)) sendo n numero primo.

As comparações vão até não haverem primos menores que o numero verificado.

Com isso da pra pensar numa maneira de expandi a arvore de decisão…

certo?

Tá bom, tá bom… digamos que você tenha o número 250000003000000009, que é igual a 500000003 vezes 500000003. Esse programa teria de ter então 500.000.003 ifs para poder dizer que o número é composto. Você conseguiria criar um programa que tem 500000003 ifs?

@David
Não… até onde tinha visto ele funcionava pra todos.

Mas não funciona em casos de primos² por exemplo 1111 ele fala que é primo 1313 e etc.

@thingol
Acho que ele quer dizer em um loop. ^^

O método não funciona para qualquer número composto que não tenha fatores 2, 3, 5 e 7. Dei o exemplo 121 (11 * 11) porque é o menor número que dá problema com esse método. Mas, por exemplo, 11 * 13 (141) dá problemas, 391 (17 * 23) dá problemas, e assim por diante.

thingol:

wallacetepes:

sem comentários… acho que meu método iterativo lento e melhor que esse… :lol:

mas até que esse metodo tem 1 boa idéia, o que eu acho q ele quis dizer Sim e "funciona… podem testar em um loop de 0 a quanto voce quiser. " é que a comparação sempre se repete if ((num % x) != 0 || (num == x)) sendo n numero primo.

As comparações vão até não haverem primos menores que o numero verificado.

Com isso da pra pensar numa maneira de expandi a arvore de decisão…

certo?

Tá bom, tá bom… digamos que você tenha o número 250000003000000009, que é igual a 500000003 vezes 500000003. Esse programa teria de ter então 500.000.003 ifs para poder dizer que o número é composto. Você conseguiria criar um programa que tem 500000003 ifs?

Leia atentamente oque escrevi… aproveitando a repetição da verificação pode se pensar em algum algoritimo que expanda arvore de decisão. O Mark_Ameba entendeu eu acho.

thingol:

Mark_Ameba:

Mas não funciona em casos de primos² por exemplo 1111 ele fala que é primo 1313 e etc.

O método não funciona para qualquer número composto que não tenha fatores 2, 3, 5 e 7. Dei o exemplo 121 (11 * 11) porque é o menor número que dá problema com esse método. Mas, por exemplo, 11 * 13 (141) dá problemas, 391 (17 * 23) dá problemas, e assim por diante.

@wallacetepes
Sim eu entendi.

http://mathworld.wolfram.com/PrimeNumber.html