Pagina 1 di 1
Algoritmo fattorizzazione
Inviato: 23/03/2015, 23:15
da doom13
Ragazzi mi servirebbe una mano sull'algoritmo di fattorizzazione. Attualmente ho usato per il metodo a forza bruta ma non è abbastanza efficiente, come potrei migliorarlo?
Re: Algoritmo fattorizzazione
Inviato: 24/03/2015, 1:10
da guidox
Ho fatto una rapida ricerca su google ed ho trovato quello di Fermat:
http://it.wikipedia.org/wiki/Metodo_di_ ... _di_Fermat
Ho provato a metterlo in codice e sembra funzionare:
Crea uno script "Fermat(numero)":
Codice: Seleziona tutto
var b2,a,b;
b2=2;
for(a=ceil(sqrt(argument0)); sqrt(b2) != floor(sqrt(b2)); a+=1) {
b2=sqr(a)-argument0;
}
a-=1;
b=sqrt(b2);
if (a-b == 1) {
ds_list_add(fattori,a+b);
}
else
if (a+b == 1) {
ds_list_add(fattori,a-b);
}
else
{
Fermat(a-b);
Fermat(a+b);
}
E poi utilizza questo codice, che metterà all'interno di una comoda ds_list i tuoi fattori primi.
Codice: Seleziona tutto
n=14153670;
fattori = ds_list_create();
while (n mod 2 == 0) {
n /= 2;
ds_list_add(fattori,2);
}
Fermat(n);
for(i=0; i<ds_list_size(fattori); i+=1) {
show_message(ds_list_find_value(fattori,i));
}
Re: Algoritmo fattorizzazione
Inviato: 24/03/2015, 8:35
da doom13
Grandissimo, in realtà mi serviva in java ma hai fatto anche troppo ci penserò io a convertirlo.
Grazie ancora.
Edit:
L'algoritmo deve essere abbastanza efficiente da calcolare la fattorizzazione di numeri a 19 cifre in 60 secondi massimo, questo ce la fa?
Re: Algoritmo fattorizzazione
Inviato: 24/03/2015, 12:42
da guidox
19 cifre O.O
Guarda con GM è impossibile farglielo fare con così tante cifre. Comunque non credo che un algoritmo di questo tipo sia la soluzione per questo problema. Ma a cosa ti serve? D:
Re: Algoritmo fattorizzazione
Inviato: 24/03/2015, 13:33
da doom13
È un esercizio. Comunque potrebbe essere che il tuo script convertito in java vada bene.
È pure ricorsiva D: la bestia hai scomodato xD
Re: Algoritmo fattorizzazione
Inviato: 24/03/2015, 15:26
da Nix
Se usi i numeri interi a 64 bit dovrebbe andar bene per la dimensione, ma per il tempo 19 cifre mi sembrano comunque troppe. Se si tratta di un problema come quelli di Project Euler, probabilmente stai sbagliando approccio.
Re: Algoritmo fattorizzazione
Inviato: 24/03/2015, 16:51
da doom13
Nix ha scritto:Se usi i numeri interi a 64 bit dovrebbe andar bene per la dimensione, ma per il tempo 19 cifre mi sembrano comunque troppe. Se si tratta di un problema come quelli di Project Euler, probabilmente stai sbagliando approccio.
E' un "semplice" esercizio, stamattina mi stavo confrontando con alcuni amici e stavamo provando ad implementare altri algoritmi, abbiamo però alcuni problemi anche se non di tempo.
Al limite vi pubblico lo pseudocodice o direttamente il codice in java magari da lì sapreste darmi una mano.
Re: Algoritmo fattorizzazione
Inviato: 24/03/2015, 18:06
da doom13
Ho convertito il codice di guidox in java ma è troppo lento
Re: Algoritmo fattorizzazione
Inviato: 24/03/2015, 22:54
da Nix
Hai detto di aver provato con la forza bruta, ma hai diviso per tutti i numeri primi da 2 alla radice quadrata del numero?
Re: Algoritmo fattorizzazione
Inviato: 25/03/2015, 1:24
da doom13
Nix ha scritto:Hai detto di aver provato con la forza bruta, ma hai diviso per tutti i numeri primi da 2 alla radice quadrata del numero?
Allora l'avevo letto in giro per internet ma sai che non l'avevo mica messo?
Attualmente l'algoritmo che ho è questo, in parte preso da internet, in parte modificato da me:
Codice: Seleziona tutto
boolean found = true;
while(found) {
found = false;
for(long i=2; i<Math.sqrt(val); i++) { //ho aggiunto quel Math.sqrt che mi ero scordato
if(val%i == 0) {
System.out.print(times + i);
val /= i;
times = " * ";
found = true;
break;
}
}
if(!found) {
System.out.println(times + val);
}
Pare funzionare e pure parecchio velocemente nonostante il numerone di prova che ho scelto (8234567890123456789) O.o
Intanto vi ringrazio, vi aggiorno per farvi sapere se sono riuscito a finire l'esercizio.
L'esercizio mi chiede di far ritornare una stringa che per 32 ad esempio è "2(3) 4". Mi rimane da aggiustarlo per far ritornare questo tipo di stringa e ho finito. Di nuovo grazie a tutti e due
Re: Algoritmo fattorizzazione
Inviato: 25/03/2015, 13:45
da guidox
Nix ha scritto:Project Euler
Figoooo
Ora mi ci diverto un po'!
Re: Algoritmo fattorizzazione
Inviato: 25/03/2015, 13:50
da Nix
Non so se effettivamente volevi questo ma così non stai fattorizzando in numeri primi, e generalmente si intende questo quando si parla di fattorizzazione (ma non necessariamente), infatti l'algoritmo di guidox (che comunque è meno efficiente della divisione) trova i fattori primi. Se vuoi fare questo puoi usare lo stesso algoritmo che stai usando per ora, controllando però anche che il numero sia primo. Ti conviene generarli tutti fino a [latex]\sqrt{n}[/latex] prima delle divisioni, per esempio col crivello di Eratostene, ma con numeri così grandi ci vuole troppa memoria e potrebbe darti dei problemi.
Re: Algoritmo fattorizzazione
Inviato: 25/03/2015, 14:42
da doom13
Allora aspetta, nell'esempio ho sbagliato a scrivere, con 32 deve restituirmi "2(5)".
Con 26 deve restituirmi "2 13", con 156 deve restituirmi "2(2) 3 13".
Quello che fa questo algoritmo è stamparmi:
156 = 2 * 2 * 3 * 13
Che è simile ma non quello che mi serve ovviamente. Devo modificarlo per far uscire quel tipo di stringa, non credo ci sia bisogno di calcolare i numeri primi fino a sqrt(n). Magari sto sbagliando eh