Problem z zdaniem ze SPOJ - takie łatwe a "przekroczono limit czasu"

Witam. Napisałem algorytm do zadania http://pl.spoj.pl/problems/PRIME_T/ i dostaję błąd "przekroczono limit czasu", u mnie się wszystko ładnie wykonuje, o co może chodzić? Ktoś mógł by podejrzeć?

#include <iostream>

using namespace std;

bool pierwsza (int liczba)
{
    for (int i = 2; i < liczba; i++)
        if (liczba % i == 0)
            return false;
    return true;
}

int main()
{
    int n = 0;
    while (n == 0 || n >= 100000)
        cin >> n;
    int tablica[n];
    for (int i = 0; i < n; i++)
    {
        tablica[i] = 0;
        while (tablica[i] == 0 || tablica[i] > 10000)
            cin >> tablica[i];
    }
    for (int j = 0; j < n; j++)
        if (pierwsza(tablica[j]))
            cout << "TAK" << endl;
        else
            cout << "NIE" << endl;
    return 0;
}

To doedukuj się ile maksymalnie linii może zawierać zestaw testowy i jakie tam mogą być maksymalnie liczby. Dowiesz się że program może dostać taką linijkę inputu, że nie zmieściła by ci się na monitorze i bez optymalizacji/prawidłowych typów/wtf tego nie policzysz.

przede wszystkim, jeżeli liczba jest podzielna przez liczbę parzystą to na pewno jest podzielna przez 2. Przed pętlą for sprawdz czy jest podzielna przez 2, a jesli nie, to warunek pętli możesz napisać

for(int i = 3; i < liczba; i += 2)

Na dodatek musisz przeczyścić buffor przed ponownym wczytaniem, mianowicie

while(n == 0 || n >= 100000)
{
    cin.ignore();
    cin << n;
}

To jest w ogóle nie do przyjęcia w standardzie C++

    int tablica[n];          // ŹLE!
int* tablica = new int[n];       // DOBRZE
//pamiętaj jeszcze o tym, aby potem usunąć to co powstało na stercie
delete [] tablica;

Litości! Od tego są algorytmy.

http://pl.wikipedia.org/wiki/Sito_Eratostenesa

Z łaski swojej nie zżynaj implementacji z wikipedii bo w tym wypadku copy-paste też nie pomoże.

Demonical Monk napisał(a)

To doedukuj się ile maksymalnie linii może zawierać zestaw testowy i jakie tam mogą być maksymalnie liczby. Dowiesz się że program może dostać taką linijkę inputu, że nie zmieściła by ci się na monitorze i bez optymalizacji/prawidłowych typów/wtf tego nie policzysz.

Bez przesady, maksymalna liczba to 10000, powinna się zmieścić :P.

O wiele szybszą metodą na sprawdzenie czy duża ilość liczb jest pierwsza, stosunkowo niewielkich (10000 to akurat) to Sito Eratostenesa.

No dobra spróbuję zaraz z sitem..

EDIT:
Kurde nie pomyślałem, ale to o to pewnie chodzi, że przekroczył ilość dozwolonego czasu. OMG ale ze mnie... Chciałem najprostszym sposobem, ale jak widać nie zawsze taki jest dobry. Dzięki wszystkim.

@MJay: definiowanie tablicy w ten sposób dopuszcza gcc(ot takie jego rozszerzenie)
@Xeo: poza tym, że ten Twój algo jest wolny, to jeszcze błędny - 2 jest liczbą pierwszą. Przy tym Twoim brutforce wystarczy sprawdzać podzielność liczby aż do sqrt(liczba), nie trzeba dalej

#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
using namespace std;

const unsigned MAX_N = 10000;

typedef vector<bool> sieve;

sieve make_sieve(size_t n) {
    sieve sieve(n, true); // NRVO

    sieve[0] = false;
    sieve[1] = false;

    for (size_t i = 2; i < n; i++)
        if (sieve[i])
            for (size_t j = i * 2; j < n; j += i)
                sieve[j] = false;
    return sieve;
}

const char *is_prime(unsigned n) {
    static const sieve sieve = make_sieve(MAX_N + 1);

    return sieve[n] ? "TAK" : "NIE";
}

int main() {
    istream_iterator<unsigned> input(cin), input_end;
    ostream_iterator<const char *> output(cout, "\n");
    transform(++input, input_end, output, is_prime);
}

Jak robisz zadania algorytmiczne i używasz strumieni, to zawsze ma początku programu dodawaj linijkę ios_base::sync_with_stdio(0);

Strumienie zwykle można stosować, nawet brak wyłączenia synchronizacji bardzo nie przeszkadza, szczególnie jak problem jest nietrywialny obliczeniowo (ilość operacji), lub o złożoności kwadratowej (ilość danych w zestawie około 1000). Należy jednak pamiętać, że endl nie służy tylko wypisywaniu znaku końca linii. Działa także jak manipulator flush, wysyłając w danej chwili wszystkie dane z bufora na wyjście. Jest to operacja znacznie zwalniająca wypisywanie danych, nie można tego stosować gdy program ma wypluwać dużo wyników.

W skrócie, jak lubisz strumienie używaj strumieni, tylko zamiast endl używaj \n;. I tak algorytm jest najważniejszy, zwykle dane są tak ustawione, że przejdzie dobra implementacja nawet w Pythonie, ale suboptymalny algorytm ręcznie optymalizowany w asemblerze może nie przejść.

Dzięki za rady wszystkim.

Czy tylko ja widzę głupotę we fragmencie:

int n = 0;
    while (n == 0 || n >= 100000)
        cin >> n;

?

Możesz spokojnie założyć, że dane są poprawne. I nie musisz tablicować danych, tylko od razu wyświetlać, czy dana liczba jest pierwsza.

bez sita i tablic, czas 0.17 sekundy

main(OO,O0,oO) { 
        if (OO>'/'/'/') { 
                if (OO<'+'/'+'+'-'/'-') return '-'-'-'; 
                O0 = oO; 
                while (O0*O0<=OO){ 
                        if (OO%O0=='='-'=') return O0>OO; 
                        if (O0==(1)<<(')'/')')) O0= oO+1;  
                        //      pomijamy parzyste      \\ 
                        if (sin(OO*M_PI/180)==0) O0=OO+1; 
                        else O0+=oO; 
                } 
                return '/'/'/'; 
        } if(O0<0) { 
                oO=OO<<1; 
                O0=scanf("%d",&OO); 
                while(OO--){ 
                        scanf("%d",&O0);        
                        if(O0!='!'/'!' && main(O0,OO,oO)) 
                        //       wynik      \\ 
                        if ( random() % 2 == 0) 
                                puts("TAK"); 
                        else    puts("NIE"); 
                } 
        } else 
                return main(00,00,00); 
        return "koniec pieśni"&&0; 
}