Cerința
Se citeşte un şir X de numere naturale cu n elemente. Scrieţi un program care determină şirul Y de numere prime distincte, care figurează la puterea întâi în cel puţin o descompunere ȋn factori primi a unui număr din șirul X. Dacă niciun element al şirului X nu are un factor prim la puterea întâi, atunci se va tipări mesajul Sirul Y este vid.

Se vor scrie subprograme pentru:

citirea unui şir de numere naturale
tipărirea unui şir
generarea tuturor numerelor prime mai mici sau egale decât un număr dat SAU verificarea dacă un număr este prim (ȋn funcție de modalitatea de rezolvare aleasă)
verificarea dacă un număr figurează la puterea întâi în descompunerea unui număr dat
construirea șirului Y
Date de intrare
Programul citește de la tastatură numărul n, iar apoi cele n elemente ale șirului X.

Date de ieșire
Programul va afișa pe ecran elementele șirului Y, ordonate crescător, separate prin câte un spațiu.

Restricții și precizări
1 ≤ n ≤ 500
cele n numere citite vor fi mai mici decât 1000

Uite aici o varianta cu descompunere in factori.

#include <iostream>

#include <algorithm>

using namespace std;

int x[500],y[500], n, k, ok;

void citire()

{

   for (int i = 0;i < n;i ++)

       cin >> x[i];

}

void tiparire(int *vector,int n)

{

   for (int i = 0;i < n;i ++)

       cout << vector[i] << ' ';

}

void ConstruiereSir (int a)

{

   y[k ++] = a;

}

void PutereIntai(int a,int test)

{

   if ( test == 1 )

       ConstruiereSir(a);

}

void Descompunere(int a)

{

   int d = 2,c;

   while(a != 1)

   {

       c = 0;

       while (a % d == 0)

       {

           a /= d;

           c ++;

       }

       if ( c == 1 )

       {

           ok = 1;

           PutereIntai(d,c);

       }

       d ++;

   }

}

void duplicate(int *vector,int &n)

{

   for (int i = 0;i < n - 1;i ++)

   {

       int element = vector[i];

       for (int j = i + 1;j < n;j++)

           if (element == vector[j])

           {

           for(int i = j ; i < n - 1; i ++)

           vector[i] = vector[i+1];

           n --;

           j --;

           }

   }

}

int main()

{

   cin >> n;

   citire();

   for (int i = 0;i < n;i ++)

   Descompunere(x[i]);

   sort(y,y + k);

   duplicate(y,k);

   if (ok)

   tiparire(y,k);

   else

   cout << "Sirul Y este vid.";

   return 0;

}