# PBinfo #2351 – numere23 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Se numește număr 3-prim, un număr natural care se poate descompune în produs de cel mult 3 numere prime, nu neapărat distincte. Cunoscând numerele naturale n și k, construiți un șir format din primele n numere 3-prime. Ordinea numerelor în șir va fi stabilită astfel încât, extrăgând pe rând numerele din șir, începând cu primul număr și apoi câte un număr din k în k poziții, circular, să obținem în ordine crescătoare, șirul primelor n numere 3-prime. Parcurgerea circulară înseamnă că după elementul aflat în vector pe locul n, urmează elementul de pe locul 1.

Cerința
Cunoscând  numerele n, k și c (c = 1 sau c = 2), se cere:
1. dacă c = 1, să se afișeze cel mai mare din cele n numere 3-prime.
2. dacă c = 2, să se construiască șirul de n numere care îndeplinește condiția din enunț.

Date de intrare
Fișierul de intrare numere23.in conţine pe prima linie, despărțite prin câte un spațiu, numerele naturale n, k și c, cu semnificaţia din enunţ.

Date de ieșire
Dacă c = 1, atunci pe prima linie a fişierului numere23.out va fi scris un singur număr ce reprezintă cel mai mare din cele n numere 3-prime. Dacă c = 2, atunci fişierul numere23.out va conţine despărțite prin câte un spațiu, șirul celor n numere 3-prime.

Restricții și precizări

0 < k < n ≤ 10000
numerotarea elementelor în vector se face de la 1

Exemplul 1:
numere23.in

5  3  2
numere23.out

2 6 4 3 5
Explicație
Primele cinci numere 3-prime sunt: 2, 3, 4, 5, și 6. Șirul de numere 2, 6, 4, 3, 5 parcurs din 3 în 3, va forma în ordine crescătoare șirul de numere inițial.

Exemplul 2:
numere23.in

10 4  2
numere23.out

2 11 10 5 3 8 7 9 4 6
Explicație
Primele 10 numere 3-prime sunt: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11.  Șirul de numere 2, 11, 10, 5, 3, 8, 7, 9, 4, 6, parcurs din 4 în 4, va forma în ordine crescătoare șirul de numere inițial.

Exemplul 3:
numere23.in

5  3  1
numere23.out

6
Explicație
Primele cinci numere 3-prime sunt: 2, 3, 4, 5, și 6. Cel mai mare număr din acest șir este 6.

## Cod sursă C++

```cpp
#include <fstream>
using namespace std;
ifstream fin("numere23.in");
ofstream fout("numere23.out");
long a[10001], b[10001], x, i, n, k;
int cer;
long urmatorul(long x);
int verif(long x);
int main()
{
    fin>>n>>k>>cer;
    x=2;
    for(i=1;i<=n;i++)
        {
        a[i]=x;
        x=urmatorul(x);
        }
    if(cer==1)                  ///cerinta 1
       fout<<a[n]<<'\n';
    else                        ///cerinta 2
    {                   ///plasez elem din a in b, parcurgand locurile libere din k in k
        b[1]=a[1];
        int p=1;
        for(i=2; i<=n; )
        {
            int m=0;  ///cate locuri libere am gasit
            if(p==n)
                p=1;
            else
                p++;
            while(m<k)      ///tb saparcurg pana la al k-lea loc liber
            {
                if(b[p]==0)
                   {
                       m++;
                       if(m==k)
                        {
                            b[p]=a[i++];m=0;
                            break;
                        }
                   }
                p++;
                if(p==n+1)
                    p=1;
            }
        }
        for(i=1;i<=n;i++)
            fout<<b[i]<<' ';
        fout<<'\n';
    }
    return 0;
}
int verif(long x)
{
    long nr=0,f=2;
    while(x%f==0)
    {
        x/=f;
        nr++;
        if(nr>3)
            return 0;
    }
    f=3;
    while(x>=f)
    {
         while(x%f==0)
         {
             x/=f;
             nr++;
         }
         if(nr>3) return 0;
         f+=2;
    }
    return nr<=3;
}
long urmatorul(long x)
{
    do
    {
        x++;
        if(verif(x))
            return x;
    }while(1);
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2351)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2351/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2351/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)