Algorytm NWD dla liczb względnie nie pierwszych

Czesc mam do napisania program ktory wyznacza kolejne wyrazy ciagu, okreslonego wzorem NWD(a_n,a_n-1)>1, wyglada on natępująco 1,2,4,6,3,9,12,8,10,5,15,18,14,7....Program na wyjsciu ma podawac index liczby w ciagu czyli dla zapytania:
IN OUT
5 10
299993 584898
300000 292101
Napisałem program, który w realizuje to zadanie:

 
   while(t_1[beg])beg++;
      n=beg; //liczba kolejna szukana to liczba ktora juz nie wystapila w ciagu
      while(NWD(i,n)==1){ //szukanie pary dla ktorej NWD>1
            if(!t_1[n])n++; //
            while(t_1[n])n++;//szukanie kolejnej liczby, ktora nie zostala wypisana
      }
      t_1[n]=index++;// liczba znaleziona zapisuje index do tb - tym samym zaznaczam liczby wypisane
      i=n; // liczba znaleziona jest poprzednia w kolejnej petli

Chciałem się zapytać czy istnieje jakiś algorytm, który w efektywniejszy sposób realizuje problem? Moja wiedza z algoytmiki nie jest zbyt duza stąd takie rozwiązanie...

opisz dokładniej definicję tego ciągu, bo ja nie rozumiem tego zapisu.

Dana jest liczba calkowita dodatnia a_n w nastepujacy sposob a₁=1, a₂=2, a_n (n>=3) jest najmniejsza liczba calkowita dodatnia, ktora do tej pory nie wystapila w ciagu i dla ktorej NWD(a_n, a_n-1)>1.

Wygląda na to, że złożoność problemu rośnie szybko rozmiarem ciągu, więc zapewne wygenerowany ciąg nie musi być bardzo długi.
Danych nie jest też bardzo dużo, dlatego napisałbym najprostszy program generujący ciąg o wystarczającej długości, a następnie wpisał twardo ten ciąg w program końcowy.

Jakie masz ograniczenie z góry na wartość wejściową? Jaki jest oczekiwany maksymalny wynik?

Pytamy o indeks liczby w tym ciagu max. liczba 30000.