Trovare il più grande numero primo che fattorizza un numero

[jegger]

Sto provando a risolvere per diletto i problemi proposti da Project Euler in Java e mi sono fermato al problema numero 3 che dice:

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?

Io ho risolto il problema, ma dicono espressamente che il problema dev'essere risolto in al massimo un minuto di computazione. Io ho risolto il problema con un escamotage, facendo un break appena individuo il maggior numero primo dato che parto dal numero più alto e scendo, ma se non ci fosse il break la computazione andrebbe avanti per non so quanto tempo.

Qualcuno sa come si possono individuare i numeri primi in maniera più efficiente?

Vi posto il testo del programmino che ho fatto:

	String problema3(){
                static long numero = 600851475143L;
		//il più grande fattore di numero sarà sicuramente inferiore alla sua metà
		long max_possible_factor = numero / 2;
		long max_prime = 0;
		for(int i = 2; i < max_possible_factor; i++){
			long reminder = numero % i;
			long factor = numero / i;
			//se il numero individuato ha resto 0, è primo ed è più grande di tutti gli
			//altri numeri primi, allora diventerà il nuovo max_prime
			if((reminder == 0) && isPrime(factor) && (factor > max_prime)){
				max_prime = factor;
				break;
			}
		}
		return "Il più grande numero primo che fattorizza "+numero+" è "+max_prime;
	}
	
    protected boolean isPrime(long num){
 
        //Il numero piu' alto per cui ha senso dividere (se si parte da 2) e'
    	//la radice quadrata del numero che stiamo testando.
    	int posMax = (int)Math.ceil(Math.sqrt(num + 1));
    	
    	//individuo i possibili divisori
        for(int divisor = 2; divisor <= posMax; divisor++)
          if (num % divisor == 0) return false;
 
        // se non ha divisori è un numero primo.
        return true;
    }

A me pare che abbia complessità n^2. Si può scendere oltre tale complessità?

[Andrea1979]

- il testo non indica espressamente di fattorizzare il numero, e quindi individuare, tra tutti i fattori primi quello maggiore: in altre parole, forzare l'uscita è lecito.

- puoi migliorare ulteriormente il tuo algoritmo:

i) quando si testa per la primalità puoi tranquillamente testare per i soli numeri DISPARI (la sola eccezione è 2) minori della radice quadrata del numero la cui primalità sia da verificare.

ii) i numeri primi, con l'eccezione di 2 e 3 sono tutti nella forma 6k +/- 1.

[desa]

"Un minuto di computazione" non ha molto senso: lo stesso algoritmo identico può girare su un vecchio Commodore 64 e su un Blue Gene IBM: ovvio che in termini di durata temporale le cose saranno molto differenti. Proprio per questo si parla di complessità
Per il test di primalità prova a dare un'occhiata (per esempio) a questa pagina di Wikipedia, magari trovi qualcosa di utile:
http://en.wikipedia.org/wiki/Primality_test

[jegger]

Vi ringrazio per la spiegazione.
Quindi a parte i miglioramenti relativi all'esclusione dei numeri pari e/o dei numeri primi visti come serie di 6k +/- 1, non si può scendere di complessità dato che la fattorizzazione di un intero è un problema difficile.

[desa]

Come miglioramenti ti posso suggerire che:
- la condizione di uscita del ciclo principale dovrebbe essere per i <= max_possibile_factor, altrimenti non funziona con i quadrati perfetti (e, a occhio, direi anche con qualunque potenza perfetta)
- se nel ciclo trovi un valore i che divide esattamente il tuo numero, puoi dividere number per quel valore e, conseguentemente ridurre il valore di max_possible_factor. A quel punto, però, devi ricordarti di "riavviare" il ciclo re-impostando i a 2 (puoi fare un prova con 12 = 2 * 2 * 3)

E' un problema classico ma sempre interessante, comunque!