Se consideră un șir de n numere întregi, cu n număr natural nenul. Se elimină primul element din șir și toate elementele șirului aflate pe poziții care reprezintă numere prime, în ordinea crescătoare a pozițiilor. Operația de eliminare se repetă cu elementele rămase în șir, repoziționate după eliminarea celorlalte, până când este eliminat și ultimul element rămas.

Cerința

Să se scrie un program care afișează elementele șirului inițial, în ordinea în care au fost eliminate conform algoritmului descris mai sus.

Date de intrare

Fișierul de intrare elimin_prime.in conține pe prima linie numărul n, iar pe a doua linie n numere întregi separate prin spații.

Date de ieșire

Fișierul de ieșire elimin_prime.out va conține pe prima linie, separate prin spațiu, numerele din fișierul de intrare în ordinea eliminării acestora.

Restricții și precizări

• 1 ≤ n ≤ 100.000
• numerele de pe a doua linie a fișierului de intrare sun cuprinse în intervalul [-1.000.000.000, 1.000.000.000]
• elementele șirului sunt indexate de la 1 la n.

Exemplul 1:

elimin_prime.in

10
1 2 3 4 5 6 7 8 9 10

elimin_prime.out

1 2 3 5 7 4 6 8 10 9

Exemplul 2:

elimin_prime.in

20
4 23 16 -7 89 115 23 11 15 2 -8 -9 21 0 75 23 32 -1 4 5

elimin_prime.out

4 23 16 89 23 -8 21 32 4 -7 115 11 2 0 5 15 -9 75 -1 23

Atenție!

Programele vor folosi doar instrucțiunile de bază ale limbajului de programare ales, inclusiv cele de intrare/ieșire, dar nu și alte funcții din biblioteci specializate (algorithm, string,…).

#include <bits/stdc++.h>
using namespace std;

ifstream cin ("elimin_prime.in");
ofstream cout ("elimin_prime.out");

struct nod
{
    int info;
    nod* urm;
};

#define Max 100010

bool ok[Max];

void Ciur()
{
    for (int i = 2; i * i < Max; i ++)
        if (!ok[i])
            for (int j = i * i; j < Max; j += i)
                ok[j] = 1;
}
void sterge(nod * p, nod * q)
{
    nod* ne = q -> urm;
    if(ne != NULL)q -> urm = ne -> urm;
    else q -> urm = NULL;

}

void adaugare(nod *&prim , nod *&ultim , int x)
{
    nod *nou = new nod;
    nou ->info = x;
    nou ->urm = NULL;
    if(prim == NULL) prim = ultim=nou;
    else
    {
        ultim ->urm = nou;
        ultim = nou;
    }
}

void afisare(nod *prim)
{
    while(prim != NULL)
    {
        cout << prim -> info << " ";
        prim = prim -> urm;
    }
}
int main()
{
    Ciur();
    int n;
    cin >> n;
    nod* prim = NULL;
    nod* ultim = NULL;
    int x;
    for (int i = 1; i <= n; i ++)
    {
        cin >> x;
        adaugare(prim , ultim , x);
    }
    //afisare(prim);

    while(n)
    {
        int s = 0 , i = 2;
        nod *p = prim;
        cout << prim ->info << " ";
        while(i <= n)
        {
            if(!ok[i])
            {
                cout << p -> urm -> info << " ";
                nod *q = p -> urm;
                p -> urm = q -> urm;
                delete q;
                s++;
            }
            else p = p ->urm;
            i++;
        }
        p = prim;
        prim = prim -> urm;
        delete(p);
        s++;
        n -= s;
    }
    return 0;
}