D@vide (Member)
Expert
Messaggi: 450
Iscritto: 30/06/2010
|
Ragazzi sto sviluppando un programmino in C# per la scomposizione di un numero che è il prodotto di numeri primi (fino a 64bit).
Prima di implementarlo tramite MPI volevo assicurarmi che non ci sia un modo più ottimizzato per risolvere il problema.
Codice sorgente - presumibilmente C++ |
using System; using System.Threading.Tasks; namespace Primen { class Factorization { public static Int64[] Factorize(Int64 k) { Int64 n = Math.Abs(k); var factors = new Int64[2]; // Escludo a priori i numeri 1 e 2 che possono essere divisibili solo per se stessi e per 1 if (n == 1 || n == 2) { factors[0] = n; factors[1] = 1; } // Controllo preventivamente che il numero non sia divisibile per 2, escludendo tutti i suoi multipli nel for successivo else if (n % 2 == 0) { factors[0] = n / 2; factors[1] = 2; } else { // Il cast è con troncamento e il ciclo Parallel.For è esclusivo del valore finale Int64 maxFactor = (Int64)Math.Ceiling(Math.Sqrt(n)) +1; var loopResult = Parallel.For(3, maxFactor, (divisor, loopState) => { if (n % divisor == 0) { factors[0] = n / divisor; factors[1] = divisor; // Fermo tutti i for in parallelo compreso quello corrente loopState.Stop(); return; } }); // Se il for è terminato senza trovare divisori, il numero è primo if(loopResult.IsCompleted) { factors[0] = n; factors[1] = 1; } } // Se il numero da fattorizzare è negativo, uno e un solo dei due numeri primi deve essere negativo if (k < 0) factors[0] *= -1; return factors; } } }
|
|
|
dnha (Member)
Pro
Messaggi: 137
Iscritto: 24/07/2014
|
|
|
D@vide (Member)
Expert
Messaggi: 450
Iscritto: 30/06/2010
|
Ciao dnha, ero all'oscuro di questo metodo, ti ringrazio anticipatamente e faccio una bella ricerca, la complessità sembra comunque minore della mia O(sqrt(n))
Nel frattempo ho notato che si parla degli algoritmi sotto il nome di "Famiglia di Kraitchik", ne hai mai sentito parlare? |
|
dnha (Member)
Pro
Messaggi: 137
Iscritto: 24/07/2014
|
Ultima modifica effettuata da dnha il 05/11/2014 alle 19:59 |
|
D@vide (Member)
Expert
Messaggi: 450
Iscritto: 30/06/2010
|
Ti ringrazio |
|