Question

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

Answer 1

#include <iostream>
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)
{
    // returnează true daca d apare la puterea 1 in descompunerea lui n
    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;
        }
}