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

Exemplul 1

Intrare

4
77 58 77 31

Ieșire

2 7 11 29 31

Exemplul 2

Intrare

4
64 36 100 125

Ieșire

Sirul Y este vid.

Exemplul 3

Intrare

4
25 5 125 5

Ieșire

5

#include <bits/stdc++.h>
using namespace std;

void Citire(int  &, int *);
void Afisare(int , int *);
void Eratostene(int *);
bool Putere1(int , int );
void Construire(int , int * , int & ,int *);

int  v[1001];

int main()
{
    int n,x[501],m,y[1001];
    Citire(n , x);
    Eratostene(v);
    Construire(n , x , m , y);
    if(m > 0)
        Afisare(m , y);
    else
        cout << "Sirul Y este vid.";
    return 0;
}

void Citire(int & n , int * x)
{
    cin >> n;
    for(int i = 1 ; i <= n ; i ++)
        cin >> x[i];
}

void Afisare(int n , int * x)
{
    for(int i = 1 ; i <= n ; i ++)
        cout << x[i] << " ";
    cout << endl;
}

void Eratostene(int * v)
{
    for(int i = 0 ; i <= 1000 ; i ++)
        v[i] = 1;
    v[0] = v[1] = 0;
    for(int i = 2 ; i * i <= 1000; i ++)
        if(v[i] == 1)
            for(int j = 2 ; i * j <= 1000 ; j ++)
                v[i*j] = 0;
}

bool Putere1(int n , int d)
{
    int p = 0;
    while(n % d == 0)
        p ++, n /= d;
    return p == 1;
}

void Construire(int n , int * x , int & m, int * y)
{
    m = 0;
    for(int i = 2 ; i <= 1000 ; i ++)
        if(v[i] == 1)
        {
            bool OK = false;
            for(int j = 1 ; j <= n  && ! OK ; j ++)
                if(Putere1(x[j] , i))
                    OK = true;
            if(OK)
                y[++m] = i;
        }
}