#include <iostream>
#include <math.h>
using std::cout;
using std::cin;


/**************************************************************************
                                     PROTOTYPY FUNKCJI
**************************************************************************/

unsigned int* generuj_tablice(const unsigned int &dlugosc);
             //zwraca pointer z zadeklarowaną tablicą
             //wypełnioną kolejnymi liczbami naturalnymi
void wyszukaj_pierwsze(const unsigned int &dlugosc, unsigned int tablica_sita[]);

unsigned int najmniejsza_poza_0(const unsigned int &dlugosc, unsigned int tablica_do_przeszukania[]);


void print_table(unsigned int const &dlugosc, unsigned int const tablica_do_wydrukowania[]);


/**************************************************************************
                                     IMPLEMENTACJE FUNKCJI
**************************************************************************/

unsigned int* generuj_tablice(const unsigned int &dlugosc)
{
     unsigned int *tablica = new unsigned int [dlugosc+1];
     for(int i=0; i<=dlugosc; i++)
       tablica[i]=i;
     return tablica;
}

void wyszukaj_pierwsze(const unsigned int &dlugosc, unsigned int tablica_sita[])
{
     unsigned int aktualny_element=2; //zaczynam od pierwszej liczby pierwszej, tabela jest od zera
     unsigned int zerowany_element;
     unsigned int pierwiastek_dlugosci = (unsigned int) sqrt(dlugosc);
     do
     {
              zerowany_element = aktualny_element*2;
              while (zerowany_element < dlugosc)
              {
                  tablica_sita[zerowany_element] = 0;
                  zerowany_element += aktualny_element;
              }
              aktualny_element = najmniejsza_poza_0(dlugosc-aktualny_element-1, &tablica_sita[aktualny_element+1]);
     }
     while (aktualny_element <= pierwiastek_dlugosci);                                
                                //przerabiamy tylko do polowy, poniewaz dalej nie ma zadnych dzielnikow 
                                //(n nie dzieli sie przez liczbe wieksza od n div 2)
}

unsigned int najmniejsza_poza_0(const unsigned int &dlugosc, unsigned int tablica_do_przeszukania[])
{
     unsigned int element=0;  //zaczynamy początku tablicy
     do
     {
              if (tablica_do_przeszukania[element] != 0)
              {
                  return tablica_do_przeszukania[element];
              }
     }
     while(element++ < dlugosc);
     return 0;
}



void print_table(unsigned int const &dlugosc, unsigned int const tablica_do_wydrukowania[])
{
     cout<<"\n\nZnalezione liczby pierwsze to:\n";
     long long tempik=0;
     for (int i=2; i<dlugosc; i++)
           if (tablica_do_wydrukowania[i]!=0) 
           {
                    ++tempik;
                    cout<</*tempik<<'-'<<*/i<<",\n";
           }
     cout<<tempik<<"\n";
}


int main()
{
    unsigned int dlugosc=0;
    unsigned int *tablica_sita=0; //pointer do tablicy, bedzie umieszczona na stercie wiec trzeba ja usunac
    do
    {
        cout<<"Podaj liczbe do ktorej mam znalesc wszystkie liczby pierwsze\n\t";
        cin>>dlugosc;
    }
    while(dlugosc==0);
    
    dlugosc++; //chodzi o to zeby pozniej tablica_sita[i] == i
               //zeby adresowanie bylo od pierwszego elementu 
    
    cout<<"Generuje tablice wypelniana kolejnymi liczbami naturalnymi.\nRozmiar tablicy:";
    if (dlugosc*sizeof(unsigned int) < 1024)
       cout <<dlugosc*sizeof(unsigned int)<<" bajtow\n";
    else
       cout <<dlugosc*sizeof(unsigned int)/1024.0<< " kilobajtow ("<<dlugosc*sizeof(unsigned int)<<"b)\n";

    
    tablica_sita = generuj_tablice(dlugosc);
    
    wyszukaj_pierwsze(dlugosc, tablica_sita);
    
    print_table(dlugosc, tablica_sita);
    
    cout<<"\n\n";
    system("pause");
    
    cout<<"Usuwam tablice sita z pamieci....\n";
    if (tablica_sita !=0) 
    {
           cout<<"Usuwam tablice sita z pamieci....\n";
           delete [] tablica_sita;
           cout<<"usunieta.\n";
    }
    return 0;
}