Faktycznie, daje się zauważyć
Czytałeś mój dopisek do twojego wątku: Cwany Lutek? Jeżeli nie to polecam
To zadanie też może być takim przykładem, że przyśpieszeniem wczytywania nic nie wskórasz.
Nawiasem mówiąc instrukcja:

nic nie ma wspólnego ze scanf/printf, więc lepiej jej nie stosować. Dotyczy ona tylko cin/cout/cerr, pod warunkiem, że jednoczenie nie korzystasz z printf i scanf.
Twoje sito ma mały błąd, liczba 1 jest liczbą pierwszą? Ale to oczywiście nie powód TLE.
Tle powoduje wielokrotne "przebieganie" tablicy i zliczanie liczb pierwszych. Czy można inaczej?
Zobacz, twoja tablica bool wygląda jakoś tak - piszę z pamięci, więc mogłem się pomylić:
000010101110101110101110

a gdyby od razu policzyć i zapisać ilość zer, liczb pierwszych [po poprawieniu twojego sita]:
001223344445566667788889 itd
012345678901234567890123 <-- to są indeksy do tablicy int
Gdy masz taką tablicę od razu możesz odpowiedzieć, w zakresie od zera do np 23 jest 9 liczb pierwszych.
A w zakresie 6 23 zapytasz? Tyle samo co wyżej - 9 ale trzeba odjąć dolny zakres - 1, czyli 9 - 3

PS
Twój program dla zakresu 0 23 wypisuje więcej - wlicza 0 i 1 jako liczby pierwsze.

PS 2
Możesz tak zmodyfikować swoje sito, rezygnując z tablicy bool na rzecz int, aby od razu zapisywać ilość liczb pierwszych, ale wtedy dodatkowo trzeba policzyć powyżej magicznej granicy i*i, ale na początek lepiej zrób to "tradycyjnie".

Witam,
znajdzie się jakaś dobra dusza, która podpowie mi jak zoptymalizować powyższy kod tak, żeby SPOJ nie wyrzucał "Przekroczono limit czasu"? Po przerobieniu wielu kombinacji rozwiązania problemu doszedłem do tego momentu i już bardziej czasu wykonania skrócić nie potrafię. Z góry dzięki za pomoc

PS. Próbowałem zgodnie ze znalezionymi na forum wskazówkami, tworzyć tablicę int'ów zawierającą ilości liczb pierwszych, czyli {0,0,1,2,2,3,3,4...}, ale w tym wariancie program się wysypuje dla testu 2 1000000.

https://ideone.com/ymGCIY38

po pierwsze program źle liczy -> twój kod + moje dana = błędne wyniki49

po drugie, źle zrozumiałeś poradę narbeja, przeczytaj jeszcze raz uważnie i zastanów się nad kolejnością działań w twoim programie - czy o to chodziło w poradzie ?

Witam wszystkich Mam problem: otóż gdy robiłem sitem eratostenesa i potem deletowałem tablicę wyskakiwał mi błąd przekroczenia limitu czasu. Natomiast gdy pomyślałem by wykorzystać poradę narbeja coś chyba szwankuje z pamięcią, bo program się zamyka od razu po włączeniu, gdy miejsc w tablicy dam 1 000 000, natomiast gdy miejsc w tablicy będzie 100 000 wszystko działa jak należy. Czy ktoś poratuje mnie i powie jak rozwiązać ten problem?

include

include

void sito(bool *tab, int n)
{
tab[1]=1;
tab[0]=1;

for ( int i=2; i*i<=n; i++)
{
    if(!tab[i])
    {
        for ( int j = i*i ; j<=n; j+=i)
            tab[j] = 1;
    }
}

}
void zamiana(bool*tab, int *tablica, int n)
{
for(int i=2; i<=n; i++)
{
if(!tab[i])
{
tablica[i]=tablica[i-1]+1;
}
else
{
tablica[i]=tablica[i-1];
}
}
}
int main()
{

bool tablica[1000001]= {};
int tablica2[1000001]= {};
sito(tablica,1000000);
zamiana(tablica, tablica2,1000000);
int test;
scanf("%d",&test);
for( int t=0; t<test; t++)
{
    int suma, dolny, gorny;

    scanf("%d%d",&dolny,&gorny);
    suma=tablica2[gorny]-tablica2[dolny-1];
    printf("%d ",suma);
}
return 0;

}`

Zadeklaruj tablicę jako globalne, tzn. poza main.

Dziękuję! Zaakceptowane : Tylko czemu to rozwiązało problem?

Witam,
Na wstępie, jest to mój pierwszy post i przepraszam za ewentualne uchybienia. Dlaczego wywala mi przekroczenie czasu? C++ 4.3.2

#include <iostream>

using namespace std;
int ile, wynik;

bool czy_pierwsza(int n)
{
  if(n<2)
    return false;

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

int main()
{
    cin >> ile;
    int * tab = new int[ile*2];

    for(int i=0; i<ile*2; i++)
    {
        cin >> tab[i];
    }


    for(int i=0; i<ile; i++)
    {
        for(int j=tab[i*2]; j<=(tab[(i*2)+1]); j++)
        {
            if(czy_pierwsza(j))
            {
                cout << "Liczba pierwsza: " << j << endl;
                wynik++;
            }
        }
        cout << wynik << endl;
        wynik = 0;
    }
    return 0;
}

skoro umiesz pisać, to może i umiesz czytać - więc przeczytaj ten wątek, jest tam odpowiedź dlaczego masz TLE

Wywala mi błąd TLE. Czy ktoś może mi powiedzieć dlaczego?

https://ideone.com/wgl25219

Jakieś usprawnienia co do programu?

Twój program za długo liczy.

Czasami łatwiej budować zupełnie od nowa, niż poprawiać czy usprawniać. I tak jest w twoim wypadku. Poszukaj i “postudiuj” tematykę liczb pierwszych. Potem wróć do zadania Liczby pierwsze [pierwsze zadanie łatwe] i popraw swój wynik [najlepsi mają tam 0,00] Gdy to zrobisz, dopiero wróć do Dyzia.

Podłączam się pod temat.
Napisałem Dyzia z użyciem tablicy wzorcowej do liczb pierwszych poniżej 1000 i przy użyciu LIST:

skoro dla 3 zakresów (bo przecież 2 z 5 są oczywiste) czas wynosi 0,15 sekundy do dla maksymalnego testu (20000 zakresów) będzie to około 1000 sekund - to chyba tłumaczy, dlaczego sędzia jest niezadowolony

Słuszna uwaga z tymi 20 ty.s zapytań zapomniałem o tym.
Jednak chyba niezbyt dokładnie przeanalizowałeś mój kod, albo ja zagmatwałem te opisy pomiaru czasu.
Wstawiam drugi raz https://ideone.com/d1IzdX8 kod, tym razem dodaję 20 ty.s testów od 1 do 1 MLN i poprawiłem opisy pomiaru czasu co jest kiedy.
Program wykonał się jak widać w 2.25529 sek, gdyż samo utworzenie bazy liczb pierwszych zajmuje 0.147636 s, pozostałe ponad 2 sek to właśnie sprawdzenie 20tys razy listy 78498 liczb pierwszych.
Czyli wadą programu jest wolne przeszukiwanie bazy szybko utworzonych listy liczb pierwszych.
Problem chyba leży w tym że nie wiem jak wykonać wyświetlenie tylko części LISTY z jakiegoś konkretnego zakresu, a być może się nawet nie dać.
Zajrzałem tu : http://www.cplusplus.com/reference/list/list/1 i widzę że jest więcej iteratorów niż begin i end, ale nadal nie mówi mi to czy da się i jak wyświetlić zawartość listy np. mniejszą / większą niż X czy Y.
Czy może lepszym rozwiązaniem byłoby tu przeniesienie tego np do tablicy o 78498 elementach?

w tym wątku opisano poprawny sposób rozwiązania tego zadania, można też rozwiązać to inaczej, też mieszcząc się w czasie
możesz więc jeszcze trochę pomyśleć, może sam wymyślisz jeden z tych sposobów (a może jest więcej niż dwa sposoby) lub przeczytać ten wątek

Rzeczywiście nie doczytałem zbyt dokładnie tego wątku wcześniej, a teraz przysiadłem na nowo po chwili przerwy i mam już AC.
Potwierdzam że porada Narbeja w tym wątku jest jednym z poprawnych rozwiązań tego zadania.
Dziękuję za pomoc.

Wywala mi błędną odpowiedź
<tu był kod>
wie ktoś może o co chodzi

Na spoju jest kilka kompilatorów c++, a wybrałeś najstarszy. W takim razie dlaczego na jednym “idzie” a na innym nie?

Nie mam pojęcia, ale może dlatego, że najnowszy kompilator potrafi “rozprawić” się z różnymi błędami i niedociągnięciami widocznymi gołym okiem w twoim kodzie, a starszy nie potrafi?