#include <iostream>
#include <ctime>

using namespace std;
int ile;

void quicksort(int *tablica, int lewy, int prawy)
{
    int v=tablica[(lewy+prawy)/2];
    int i,j,x;
    i=lewy;
    j=prawy;
    do
    {
        while(tablica[i]<v) i++;
        while(tablica[j]>v) j--;
        if(i<=j)
        {
            x=tablica[i];
            tablica[i]=tablica[j];
            tablica[j]=x;
            i++;
            j--;
        }
    }
    while(i<=j);
    if(j>lewy) quicksort(tablica,lewy, j);
    if(i<prawy) quicksort(tablica, i, prawy);
}
bool czy_pierwsza(int n)
{
    if(n<2)
        return false; //gdy liczba jest mniejsza niż 2 to nie jest pierwszą

    for(int i=2;i*i<=n;i++)
        if(n%i==0)
            return false; //gdy znajdziemy dzielnik, to dana liczba nie jest pierwsza
    return true;
}

int main()
{
    cout << "Ile losowych liczb w tablicy: ";
    cin >> ile;

    //dynamiczna alokacka tablicy
    int *tablica;
    tablica = new int [ile];


    //inicjowanie generatora
    srand(time(NULL));
    cout << "Przed posortowaniem: " << endl;
    //wczytywanie losowych liczb do tablicy
    for(int i=0; i<ile; i++) {
        tablica[i] = rand() % 10 + 1;
        cout << tablica[i] << " ";
    }



    quicksort(tablica, 0, ile-1);


    cout << endl << "Po posortowaniu: " << endl;
    for(int i=0; i<ile; i++)
    {
        cout << tablica[i] << " ";
    }

    //liczby pierwsze
    cout << endl << "Liczby pierwsze: " << endl;
    for(int i=0; i<ile; i++) {
        if (czy_pierwsza(tablica[i]) == 1) {
            int liczba_pierwsza = tablica[i];
            tablica[i] = liczba_pierwsza;
            cout << tablica[i] << " ";
        }
    }

    delete [] tablica;

    return 0;
}