# PBinfo #2767 – masterpiece003 – Rezolvare C++

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

## Enunț

Cerința
Se consideră două numere naturale n și k. 
Se consideră P = { p1 , p2 , p3  … pk } , șirul primelor k numere prime. 
Se consideră mulțimea S = { x | x = p1e1 * p2e2 * … * pkek } unde e1 , e2 , e3  … ek sunt numere naturale.
Să se afișeze în ordine crescătoare primele n elemente mulțimii S.

Date de intrare
Programul citește de la tastatură numerele n și k.

Date de ieșire
Programul afișează pe ecran, în ordine crescătoare, separate prin câte un spațiu, primele n elemente ale mulțimii S.

Restricții și precizări

1 ≤ n ≤ 100000
1 ≤ k ≤ 10
Se garantează că elementele mulțimii S sunt numere naturale care se pot reprezenta pe 8 octeți.

Exemplu:
Intrare

40 5
Ieșire

1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 18 20 21 22 24 25 27 28 30 32 33 35 36 40 42 44 45 48 49 50 54 55 56 60 63
Explicație
Oricare dintre numerele afișate conțin în descompunerea lor în factori primi doar factori din mulțimea {2, 3, 5, 7, 11}. 
Din șirul afișat lipsesc numerele care au în descompunerea lor în factori primi și alte numere în afară de 2, 3, 5, 7, 11. De exemplu numărul 26 nu va fi afișat pentru că, în decompunerea lui apare factorul 13.

## Cod sursă C++

```cpp
///O(n)                    O(n*k) cu k mic - 100 de puncte
#include "iostream"
using namespace std;
unsigned long long s[100100];/// Solutie
int p[100]{0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29};/// Numere prime
int d[100]{0, 1, 1, 1, 1,  1,  1,  1,  1,  1,  1};/// Indici pentru calcul candidati
unsigned long long c[100]={0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29};/// Candidati
int main(){
    int n, k;
    cin >> n >> k;
    s[1] = 1;
    for(int i=2 ; i<=n ; ++i){
        unsigned long long minim = c[1];
        for(int i=1 ; i<=k ; ++i)
            if(c[i] < minim)
                minim = c[i];
        s[i] = minim;
        for(int j=1 ; j<=k ; ++j)
            if(c[j] == minim)
                c[j] = s[++d[j]] * p[j];
    }
    for(int i=1 ; i<=n ; ++i)
        cout << s[i] <<' ';
}
```

## Resurse

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