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.

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?

Dzieki działa usuwam kod