#include <iostream>
#include <cstdlib>
#include <cmath>
 
using namespace std;
 
bool esPrimo(unsigned int num);
void Quicksort(int *unarray, int izq, int der);
int pivot(int *unarray, int izq, int der);
 
int main(int argc, char *argv[])
{
    int *arrayDeNumeros= (int*) calloc(1000,sizeof(int*));
    int lenArray = 0;
    cout << "Ingrese una cadena de numeros terminada en 0:" << endl;
    cin>>arrayDeNumeros[0];
    for(register int i = 1; arrayDeNumeros[i-1]!=0 ; ++i)
    {
        cin>>arrayDeNumeros[i];
        lenArray = i;
    }
    /** El algoritmo que viene a continuación lo que hace
     *  es ordenar  el array  arrayDeNumeros de  menor  a
     *  mayor,sinceramente,no sé como funciona solo que he
     *  leído que era rápido y lo he buscado.
     */
 
    Quicksort(arrayDeNumeros,0,lenArray);
    /**
     *  El siguiente bucle mira si los enteros que ya están
     *  ordenados son primos o no.
     */
    for(register int i = 1; arrayDeNumeros[i]!=0; ++i)
    {
        if(esPrimo(arrayDeNumeros[i]))
            cout<<"El numero "<<arrayDeNumeros[i]<<" es primo."<<endl;
        else
            cout<<"El numero "<<arrayDeNumeros[i]<<" no es primo."<<endl;
    }
    return 0;
}
 
void Quicksort(int *unarray, int izq, int der)
{
    int pivote;
    if(izq < der)
    {
        pivote=pivot(unarray, izq, der);
        Quicksort(unarray, izq, pivote-1);
        Quicksort(unarray, pivote+1, der);
    }
}
int pivot(int *unarray, int izq, int der)
{
    int i;
    int pivote, valor_pivote;
    int aux;
 
    pivote = izq;
    valor_pivote = unarray[pivote];
    for (i=izq+1; i<=der; i++)
    {
        if (unarray[i] < valor_pivote)
        {
            pivote++;
            aux=unarray[i];
            unarray[i]=unarray[pivote];
            unarray[pivote]=aux;
 
        }
    }
    aux=unarray[izq];
    unarray[izq]=unarray[pivote];
    unarray[pivote]=aux;
    return pivote;
}
bool esPrimo(unsigned int num)
{
    if(num>2 && (num%2==0))/* Si el número es mayor que 2 y es divisible por el entonces no es primo*/
        return false;
    /**
     * Para comprobar si un número es primo se suele
     * utilizar el siguiente algoritmo, que consiste
     * en llegar hasta la raiz cuadrada del número de
     * dos en dos y empezando en 3, ya que un número
     * que no es par en la vida puede ser dividido por
     * un par.
     */
    unsigned int numSquare = (unsigned int)sqrt(num);
    for(register unsigned int i =3; i<=numSquare ; i+=2)
    {
        if(num%i==0)
        {
            return false;
        }
    }
    return true;
}