[C++] Scomposizione in fattori primi troppo lenta

[Ippo343]

Ciao a tutti, stavo provando il problema 583 di UVA Online Judge, 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]

L'algoritmo di ricerca dei numeri primi mi pare un po' tanto forza bruta...

[ant_alt]

[ot] non ho capito che vuol dire limite 3 secondi
puoi spiegarmi in due parole in che consistono questi problemi? l'inglese lo spicco poco

[Ippo343]

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]

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.