#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(wsk->status==true){
            Prim *wsk2=wsk;
            for(j=2*i;j<=n;j++){

                if(j%i==0){
                    wsk2=wsk2->next;
                    wsk2->status=false;

                    cout<<wsk2->x<<endl;
                }
                    else wsk2=wsk2->next;
                    cout<<"W elsie: "<<j<<endl;
            }


        }
        wsk=wsk->next;

    }

   Prim *temp=head; //poczatek wyswietlania elementow listy
	cout<<"Liczby pierwsze z danego przedzialu to:"<<endl;
	while(temp!=NULL){ //wyswietlanie elementow listy ze statusem true
		if(temp->status==true){
            cout<<temp->x<<endl;
            temp=temp->next;
        }
        else temp=temp->next;


	}

    return 0;
}