Algoritmo fattorizzazione
- doom13
- Moderatore
- Messaggi: 2093
- Iscritto il: 31/08/2012, 15:40
- Specialità: Programmazione
- Uso: GM:Studio 2
- Contatta:
Algoritmo fattorizzazione
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?
Spoiler
"Things get hard sometimes guys... But remember, dicks get hard too, but they don't stay hard forever. Don't give up!"
- guidox
- GMI Honor
- Messaggi: 5765
- Iscritto il: 26/07/2009, 17:23
- Specialità: programmazione
- Uso: GM:Studio 1.4 Android
- Località: Marche
- Contatta:
Re: Algoritmo fattorizzazione
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)":
E poi utilizza questo codice, che metterà all'interno di una comoda ds_list i tuoi fattori primi.
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);
}
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));
}
- doom13
- Moderatore
- Messaggi: 2093
- Iscritto il: 31/08/2012, 15:40
- Specialità: Programmazione
- Uso: GM:Studio 2
- Contatta:
Re: Algoritmo fattorizzazione
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?
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?
Spoiler
"Things get hard sometimes guys... But remember, dicks get hard too, but they don't stay hard forever. Don't give up!"
- guidox
- GMI Honor
- Messaggi: 5765
- Iscritto il: 26/07/2009, 17:23
- Specialità: programmazione
- Uso: GM:Studio 1.4 Android
- Località: Marche
- Contatta:
Re: Algoritmo fattorizzazione
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:
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:
- doom13
- Moderatore
- Messaggi: 2093
- Iscritto il: 31/08/2012, 15:40
- Specialità: Programmazione
- Uso: GM:Studio 2
- Contatta:
Re: Algoritmo fattorizzazione
È un esercizio. Comunque potrebbe essere che il tuo script convertito in java vada bene.
È pure ricorsiva D: la bestia hai scomodato xD
È pure ricorsiva D: la bestia hai scomodato xD
Spoiler
"Things get hard sometimes guys... But remember, dicks get hard too, but they don't stay hard forever. Don't give up!"
Re: Algoritmo fattorizzazione
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.
- doom13
- Moderatore
- Messaggi: 2093
- Iscritto il: 31/08/2012, 15:40
- Specialità: Programmazione
- Uso: GM:Studio 2
- Contatta:
Re: Algoritmo fattorizzazione
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.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.
Al limite vi pubblico lo pseudocodice o direttamente il codice in java magari da lì sapreste darmi una mano.
Spoiler
"Things get hard sometimes guys... But remember, dicks get hard too, but they don't stay hard forever. Don't give up!"
- doom13
- Moderatore
- Messaggi: 2093
- Iscritto il: 31/08/2012, 15:40
- Specialità: Programmazione
- Uso: GM:Studio 2
- Contatta:
Re: Algoritmo fattorizzazione
Ho convertito il codice di guidox in java ma è troppo lento
Spoiler
"Things get hard sometimes guys... But remember, dicks get hard too, but they don't stay hard forever. Don't give up!"
Re: Algoritmo fattorizzazione
Hai detto di aver provato con la forza bruta, ma hai diviso per tutti i numeri primi da 2 alla radice quadrata del numero?
- doom13
- Moderatore
- Messaggi: 2093
- Iscritto il: 31/08/2012, 15:40
- Specialità: Programmazione
- Uso: GM:Studio 2
- Contatta:
Re: Algoritmo fattorizzazione
Allora l'avevo letto in giro per internet ma sai che non l'avevo mica messo?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?
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);
}
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
Spoiler
"Things get hard sometimes guys... But remember, dicks get hard too, but they don't stay hard forever. Don't give up!"
Re: Algoritmo fattorizzazione
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.
- doom13
- Moderatore
- Messaggi: 2093
- Iscritto il: 31/08/2012, 15:40
- Specialità: Programmazione
- Uso: GM:Studio 2
- Contatta:
Re: Algoritmo fattorizzazione
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
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
Spoiler
"Things get hard sometimes guys... But remember, dicks get hard too, but they don't stay hard forever. Don't give up!"
Chi c’è in linea
Visitano il forum: Nessuno e 6 ospiti