PDA

Visualizza la versione completa : [C++] Scomposizione in fattori primi troppo lenta


Ippo343
16-09-2009, 23:02
Ciao a tutti, stavo provando il problema 583 di UVA Online Judge (http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=524), e penso di esserci riuscito.

Le specifiche dicono che viene passato un file che contiene su ogni linea un numero compreso tra -2^31 e +2^31, e chiede di stamparne la fattorizzazione. L'ultima riga è uno 0 che chiude il file.

In ogni mio test funziona perfettamente. Però il problema non viene accettato per "Time Limit Exceeded". Il tempo limite è di 3 secondi. L'algoritmo pare funzionare, però evidentemente vengono passati dei numeri troppo grandi e il mio algoritmo è troppo lento.

Purtroppo non posso sapere che file (e quindi quanti e quali numeri) vengono passati al programma...



#include <iostream>
#include <math.h>

using namespace std;

//Checks wether a number is prime
bool IsPrime(long n)
{
//Sets the maximum factor to be tested
//as the square root of the number
long limit = (long)(sqrt(n) + 1);

for (int i = 2; i < limit; i++)
if ((n % i) == 0) return false;

return true;
}

void PrintFactors(long n)
{
cout << n << " = ";
bool alreadyPrinted = false;

//Prints -1 and makes the number positive
if (n < 0)
{
cout << "-1";
alreadyPrinted = true;
n *= -1;
}

long factor = 2;

//Repeat while the number
//can still be divided
while (n > 1)
{
//Repeats while the number can be divided
//by the current factor
while ((n % factor) == 0)
{
if (alreadyPrinted) cout << " x ";
cout << factor;
alreadyPrinted = true;

n /= factor;
}

//Finds next prime factor
do
{
factor++;
}
while (!IsPrime(factor));
}

cout << "\n";
}

int main()
{
long readNumber = 0;

cin >> readNumber;

while (readNumber)
{
PrintFactors(readNumber);
cin >> readNumber;
}

return 0;
}

MItaly
17-09-2009, 00:12
L'algoritmo di ricerca dei numeri primi mi pare un po' tanto forza bruta...

ant_alt
17-09-2009, 00:34
[ot] non ho capito che vuol dire limite 3 secondi :fagiano:
puoi spiegarmi in due parole in che consistono questi problemi? l'inglese lo spicco poco :fagiano:

Ippo343
17-09-2009, 00:38
TUTTO è forza bruta xD

A quale parte ti riferivi?

Questa?


bool IsPrime(long n)
{
//Sets the maximum factor to be tested
//as the square root of the number
long limit = (long)(sqrt(n) + 1);

for (int i = 2; i < limit; i++)
if ((n % i) == 0) return false;

return true;
}


O questa?


//Finds next prime factor
do
{
factor++;
}
while (!IsPrime(factor));

MItaly
17-09-2009, 01:16
Entrambe. :) Esistono metodi molto più efficienti per cercare numeri primi; inoltre invece di ricercarli ogni volta per ogni numero dovresti farti una tabella di numeri primi, e aggiungere di volta in volta solo quelli che non hai ancora trovato.

Loading