Cerința

Se dă un tablou cu n elemente, numere naturale. Să se înlocuiască fiecare element din tablou care nu este număr prim cu cel mai mic număr prim, mai mare decât el.

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
• prim, care verifică dacă un număr natural este prim
• urmatorul_prim, care determină pentru un număr dat cel mai mic număr prim, mai mare decât acesta, folosind subprogramul prim
• 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, 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

7 19 19 5 17 23 5

#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];
}

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

int urmatorul_prim(int n){
    if(n == 0 || n == 1)
        return 2;
    if(n % 2 == 0)
        n++;
    while(!prim(n))
        n+=2;
    return n;
}

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

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){
        if(!prim(a[i]))
            inloc(a, i, urmatorul_prim(a[i]));
    }

    afisare(n, a);
    return 0;
}