SPOJ-Problem Dyzia

Question

Witam!

Mam problem z zadaniem ze spoja .Mianowicie nie akceptuje mi kodu wyświetlając komunikat:Przekroczono limit czasu.Proszę więc o pomoc o usprawnienie mego programu.Przesyłam link do treści zadania :http://pl.spoj.com/problems/DYZIO2/ .

#include<iostream>
#include<cstdlib>

using namespace std;
bool czy_pierwsza(int n)
{
  if(n<2)
    return false;
  for(int i=2;i*i<=n;i++)
  {


    if(n%i==0)
      return true;
   }
      return false;
}

int main()
{
int k;
cin>>k;
int a[k];
int b[k];
int p[k];


for( int i=1;i<=k;i++ )
{
    cin>>a[i]>>b[i];
}
for( int i=1;i<=k;i++ )
{
   p[i]=0;
}
for(int i=1;i<=k;i++)
{


   for(int j=b[i];j>=a[i];j--)
   {



   if(czy_pierwsza(j)!=1)
    {


    p[i]++;
    }



}
}


for( int i=1;i<=k;i++ )
{
    cout<<p[i]<<endl;
}


  return 0;
}

 

 

Answer 1

#include możesz chyba usunąć. Słyszałem też, że preinkrementacja/predekrementacja jest szybsza od post.

Comments

<cstdlib> rzeczywiście nie jest potrzebne (nieistotne z punktu widzenia optymalizacji), ale skąd wziąłeś tę preinkrementację (pomijając marginalny wpływ tego na wydajność) ? Pół kompilatora by zrozumiało, że samodzielne i++ jest równoznaczne z ++i dla intów.

---

Równoznaczne może jest. Zadziałało?

Answer 2

przy każdej iteracji :

 for(int i=2;i*i<=n;i++)   obliczasz i*i - to jest dosyć czasochlonne

może najpierw policz k=sqr(n) tylko raz się to policzy

a pętla for ( int i<2;i<=k;i++)

 

a może jest jakiś szybszy algorytm określania liczy pierwszej ?