[c++] Liczby pierwsze - "przekroczono limit czasu"

Witam.

Rozwiązuje zadania ze strony SPOJ.
Trafiło mi się takie zadanie z liczb pierwszych, którego sędzia nie chce zaakceptować - mianowicie "przekroczony limit czasu"

Oto moje rozwiązanie:

 #include<iostream>
using namespace std;

int date(int l, int c, int tab[])
{
    static int a=0;
    for(int i=1; i<=l; i++)
    {
            if(l%i==0)c++;
            if(l==i){tab[a]=c; a++;}
    }
};
int main()
{
    int lt, l, k=1;
    cin>>lt;
    int *tab = new int [lt];
    while(k<=lt)
    {
       cin>>l;
       date(l,0,tab);
       k++;
    };
    for(int j=0; j<lt; j++)
            if(tab[j]==2) cout<<"TAK"<<endl;
            else cout<<"NIE"<<endl;
   
    delete[] tab;  

    return 0;
}

Kod sie skompiluje, ale problem jest z czasem, którego sędzia nie chce zaakceptować... dlatego proszę o pomoc.

jeżeli masz za zadanie stwierdzić, czy liczba jest pierwsza, to wcale się nie dziwie, że przekraczasz limt.Juz nie mówiąc o zdziwieniu, że wynik jest dobry..

Google => Sito Eratostenesa

@gubbi rzuć okiem na limity pamięci. Jeśli są wystarczające żeby połknąć tablicę rozmiaru maks_liczba bajtów to zrób tak:
-napisz poprawny algorytm sprawdzający czy dana liczba jest pierwsze (od razu mówię że pętla od 1 do n sprawdzająca czy n dzieli się bez reszty przez kolejne liczby, to jest złe rozwiązanie, da się znacznie szybciej)

• następnie na początku programu puszczasz pętelkę od 1 do maks_liczby i wypełniasz tą tablicę

bool isPrime(int liczba);
int main()
{
  bool tablica[MaxLiczba];
  for(int i=0;i<MaxLiczba;i++)
    tablica[i] = isPrime(i);
  //dalsze instrukcje
  return 0;
}

W dalszej części pobierasz ze spoja liczbę do sprawdzenia i w tablica[liczba] masz odpowiedź czy jest pierwsza czy nie.

od razu mówię że pętla od 1 do n sprawdzająca czy n dzieli się bez reszty przez kolejne liczby, to jest złe rozwiązanie, da się znacznie szybciej
najprostszym przyspieszeniem bedzie sprawdzanie nie od 1 do n (a w zasadzie od 2 do n-1) tylko do sqrt(n).

Bez użycia sita Erastotenesa policzyłem ile jest liczb złożonych w przedziale [1,zakres].
1.Algorytm "naiwny":

        for(int i=1;i<=zakres;i++)
        {
            for(int j=2;j<i-1;j++)
            {
                if(i % j==0)
                {
                    ileJest++;
                    break;
                }
            }
        }
</cpp>
2.Algorytm ulepszony:
```cpp
        for(int i=1;i<=zakres;i++)
        {
            if((i>2) && i % 2==0)
            {
                ileJest++;
            }
            else
            {
                double gr=Math.sqrt(i);
                for(int j=3;j<=gr;j+=2)
                {
                    if(i % j==0)
                    {
                        ileJest++;
                        break;
                    }
                }
            }
        }

Czasy wykonania (w ms.) A.1 A.2
zakres=1000 3,8 0,01
zakres=10000 96,2 1,25
zakres=100000 7389,9 24,88
zakres=1000000 608075,4 575,89

Mała porada, tych liczb jest na tyle mało, że można je wszystkie wcisnąć w jednego switch'a lub do jednej wielkiej tablicy.

zastanawiam się jak zmodyfikować Sito Eratostenesa, tak żeby program działał jak wcześniejszy i zmieścił się dla zakresu 100000 w czasie do 0,00 sekund

treść problemu https://pl.spoj.pl/problems/PRIME_T/

Gubbi, mi się to nie udało mimo wstawienia tablicy liczb pierwszych na sztywno do programu, więc jeśli ty je generujesz w trakcie działania to nie widzę szans dla Ciebie przy zejściu do 0.00s

ale są tacy hardcorzy którym się to udało... :D

Musieli używać szybkiego wczytywania danych, ale nie mam pojęcia jak je potem przetworzyli. strtok() nie zdało egzaminu.