Witam piszę tutaj po raz któryś. Ucze się jakiś miesiąc języka c++ (Łącznie z przerwami) i mam cały czas problem z optymalizacją kodu do jak najlepszej złożoności.
Zadanie oczywiście ze spoj-a polega na wyznaczeniu liczb pierwszych w zakresie. Problem? Przekroczono limit czasu:/
Ma ktoś wiedzę dzięki czemu mogę to lepiej zoptymalizować? Szukając w internecie znalazłem kilka innych ale prawie wszystkie bazują na tym samym.
Proszę jedynie o informacje która bilbioteka lub co może tutaj pomóc, dalej sam już znajdę nie chcę żebyście rozwiązywali problem za mnie.
Link do zadania: https://www.spoj.com/problems/PRIME1/
Kod mojego brzydala:
#include <iostream>
#include <math.h>
using namespace std;
void licz(long long int &a, long long int &b)
{
bool *zbior= new bool[b+1];
for(int i=2; i<=b; i++)
{
zbior[i]=true;
}
for(int i=2; i<=sqrt(b); i++)
{
if(zbior[i]==true)
{
for(int j=i*i; j<=b; j+=i)
{
zbior[j]=false;
}
}
}
for(int i=2; i<=b; i++)
{
if((zbior[i]==true)&&(i>=a))
{
cout<<i<<endl;
}
}
}
int main()
{
int proby;
long long int zakres1,zakres2;
cin>>proby;
while(proby!=0)
{
cin>>zakres1>>zakres2;
while((1>zakres1>zakres2>1000000000)||(zakres2-zakres1>100000))
{
cout<<"Zle wpisane dane, wpisz ponownie liczby musza spelniac warunki 1 <= a <= b <= 1000000000, b-a<=100000, nie rozpoczniesz zadania dopoki tego nie zrobisz."<<endl;
cin>>zakres1>>zakres2;
}
licz(zakres1,zakres2);
proby--;
}
return 0;
}
