[C++] Jak przyspieszyć działanie programu?

Dla specjalistów Programowanie
#1

Witam.

Napisałem program w C++, który wypisuje którąś z kolei liczbę pierwszą.

Np.

Wejście

3 - ilość przypadków

1 - muszę wypisać pierwszą liczbę pierwszą

2 - muszę wypisać drugą liczbę pierwszą

3 - muszę wypisać trzecią liczbę pierwszą

 

Wyjście

2 - pierwsza liczba pierwsza

3 - druga liczba pierwsza

5 - trzecia liczba pierwsza

 

To jest mój kod:

#include <iostream>
#include <vector>
#include <stdio.h>
#include <math.h>
using namespace std;

int main()
{
   int r, a, b=1, i, c=0;
   vector<int> tab1;
   tab1.push_back(2);
   vector<int> tab2;
   scanf("%d",&r);
   for(int i=0; i<r; i++)
   {
      scanf("%d",&a);
      tab2.push_back(a);
      if(a>b)
      b=a;
   }
   for(i=3; tab1.size()<b; i++)
   {
      for(int j=0;tab1[j]<=sqrt(i);j++)
      {
         if(i%tab1[j]==0)
         {
            c=1;
            break;
         }
      }
      if(c==0) tab1.push_back(i);
      c=0;
   }
for(i=0; i<r; i++) printf("%d \n",tab1[tab2[i]-1]);
return 0;
}

Nie wiem co zrobić by go jeszcze przyspieszyć lub zoptymalizować.

#2

Jakie ograniczenie na a?

#3
  1. pisz tak zeby kod byl przejrzysty, wcięcia

 

if(c==0)
{
tab1.push_back(i);
}

to jest to samo co

if(c==0) tab1.push_back(i);

3

for(i=0; ir; i++)
{
printf("%d",tab1[tab2[i]-1]);
printf ( "\n");
}

=

for(i=0; ir; i++) printf("%d \n",tab1[tab2[i]-1]);
#4

Od 1 do 78 498.

#5

Dla tak małego przedziału jak milion możesz albo zastosować sito albo hardcoding. Więcej podpowiedzi nie dostaniesz, bo capi SPOJem z metra.

#6

Dzięki spróbuję.

P.S. To nie jest SPOJ tylko zadanie na kółko w szkole, z którym miałem problem.

#7

Możliwe, nie mniej: słowa kluczowe w google wskazują na to coś, albo coś bardzo podobnego: google-> spoj prime 78498

#8

To co napisał @Agron na pewno nie przyśpiesza programu (bo nie ma żadnego związku z algorytm) a do tego moim zdaniem (jak

pewnie wielu innych doświadczonych programistów) zaciemnia kod.

Radziłbym nie stosować tamtej podpowiedzi. Pozostawień klamer daję większą przejrzystość kodu i pozwala uniknąć błędu kiedy dany blok jest rozszerzany o kolejną instrukcję,

 

Można jedynie złączyć poniższe wywołanie:

printf("%d",tab1[tab2[i]-1]);
printf ( "\n");

na

printf("%d \n",tab1[tab2[i]-1]);

ale klamry zostawiłbym.

 

Druga uwaga: Staraj się nazywać zmienne jak najbardziej zrozumiale. Nazyw tab1, tab2 nie wiele mówią.

Trzecia uwaga: Deklarowanie zmiennych powinieneś robić jak najbliżej miejsca ich użycia. np zamiast deklarować zmienną “i” na początku programu możesz ją deklarować w bloku for (jak to zrobiłeś w pierwszej pętli).

 

Btw nie edytuj swoich postów poprawiając kod bo też zaciemnia zrozumienie konwersacji.

 

=====================

Ok temat optymalizacji. Kolega @kostek135 podał Ci już kilak słów kluczowych o które warto przepytać wujka google. Ja skupił bym się trochę na poniższej pętli:

for(i=3; tab1.size()<b; i++)
   {
      for(int j=0;tab1[j]<=sqrt(i);j++)
      {
         if(i%tab1[j]==0)
         {
            c=1;
            break;
         }
      }
      if(c==0) tab1.push_back(i);
      c=0;
   }

Jak rozumiem jest to pętla wyszukująca kolejne liczby pierwsze. Parametr “i” jest kandydatem na kolejną liczbę pierwszą. Inkrementując wartość i o jeden sprawdzamy także liczby parzyste. W przypadku inkrementowania o wartość 2 algorytm na tej pętli eliminuje połowę sprawdzeń.