#include <iostream>
#include <cstdlib>
#include <math.h>
#include <new>

using namespace std;

struct Prim //struktura z jedna liczba
{
    int x; //wartosc podanej liczby
    bool status; //status: true - liczba pierwsza, false - nie liczba pierwsza
    Prim *next; //wskaznik na nastêpny element listy
};


int main()
{
    int n,i,j,maxi;
    Prim *head = NULL; //deklaracja glowy i nadanie jej adresu zerowego
    Prim *tail = NULL; //deklaracja ogona i nadanie jej adresu zerowego
    Prim *nowy;

    cout<<"Podaj zakres liczb ";
    cin>>n;

    for(i=2; i<=n; i++) //tworzy liste
    {
        nowy=new Prim; //tworzenie nowego obiektu typu prim

        nowy->next=NULL; //nastepny element wskazuje na NULL
        nowy->x=i; //nadanie wartosci liczby takiej jaka jest w danej iteracji
        nowy->status=true; //domyslnie kazda liczba ma status true

        if(head==NULL)//sprawdza czy zostal juz utworzony pierwszy element listy
        {
            head=nowy; //glowa przyjmuje adres pierwszego elementu
            tail=head; //ogon tez wskazuje na pierwszy element, bo to jest pierwszy element listy
        }
        else
        {
            tail->next=nowy; //jesli lista zawiera juz pierwszy element, ogonowi dajemy wskaznik nastepnego elementu
            tail=nowy;
        }
    }

    maxi=sqrt(n); //tworzenie warunku stopu, czyli do jakiej liczby ma sie wykonywac algorytm sita
    Prim *wsk=head; //pomocniczy wskaznik do przeszukiwania listy
    for(i=2; i<=maxi; i++) //iteracja wykonuje się tylko dla wielokrotnosci liczb  nie wiekszych od maxi
    {
        if(head->x==i)

        {
            j=i+i;

            while(j<=n)
            {

                if(wsk->x==j)
                {
                    wsk->status=false;
                    wsk=wsk->next;
                    j+=i;
                }
                else
                {
                    wsk=wsk->next;
                    j+=i;
                }
            }
        }
    }

    Prim *temp=head; //poczatek wyswietlania elementow listy
    while(temp!=NULL)
    {
        if(temp->status=true)
            cout<<temp->x<<endl;
        temp=temp->next;

    }

    return 0;
}