Cerința

Pentru un număr natural x mai mare decât 1 numim redusul lui x cel mai mic număr natural care are exact aceiași divizori primi ca și x.

Se dă un tablou cu n elemente, numere naturale mai mari decât 1. Să se înlocuiască fiecare element din tablou cu redusul său și apoi să afișeze elementele din tabloului ordonate descrescător.

Se vor defini și apela următoarele subprograme:

• citire, care citește de la tastatură valoarea lui n și cele n elemente ale tabloului
• afisare, care afișează pe ecran elementele tabloului, separate prin exact un spațiu
• redus, care determină pentru un număr dat redusul său
• sortare, care sortează descrescător un tablou
• inloc, care realizează înlocuirile cerute.

În programele C/C++ nu se vor folosi variabile globale.

Date de intrare

Se citește de la tastatură numărul n, iar apoi cele n elemente ale tabloului.

Date de ieșire

Se vor afișa pe ecran elementele tabloului după transformările cerute, separate prin exact un spațiu.

Restricții și precizări

• 1 ≤ n ≤ 1000
• elementele tabloului vor fi mai mici decât 1.000.000.000

Exemplu

Intrare

7
7 18 18 5 14 20 4 

Ieșire

14 10 7 6 6 5 2

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

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

int redus(int n){
    int nr = 1;
    int d = 2;
    while(n > 1){
        int p = 0;
        while(n % d == 0)
            n/=d, p++;
        if(p > 0)
            nr *= d;
        d++;
        if(d * d > n)
            d = n;
    }
    return nr;
}

void inloc(int a[], int i, int r){
    a[i] = r;
}

void sortare(int n, int a[]){
    for(int i = 1; i < n; ++i)
        for(int j = i + 1; j <= n; ++j)
            if(a[j] > a[i])
                swap(a[i], a[j]);
}

void afisare(int n, int a[]){
    for(int i = 1; i <= n; ++i)
        cout << a[i] << " ";
}

int main()
{
    int n, a[1001];
    citire(n, a);
    for(int i = 1; i <= n; ++i){
        int r = redus(a[i]);
        inloc(a, i, r);
    }
    sortare(n, a);
    afisare(n, a);
    return 0;
}