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...

codice:
#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;
}