Question

Se numeşte număr prim, un număr care este divizibil doar cu 1 şi cu el însuşi. Astfel în intervalul [1, 30] numerele prime vor fi: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, în total 10 numere prime.

Notă: Numărul 1 nu este considerat număr prim!

Cerinţă:
Dându-se două numere n, k să se determine 2*k numere prime situate în centrul listei numerelor prime din intervalul [1, n], în cazul în care în interval este un număr par de numere prime şi 2*k-1 numere din centrul listei de numere prime, în cazul în care numărul de numere prime este impar.

Dacă numărul 2*k (respectiv 2*k-1) este mai mare decât numărul de numere prime din intervalul considerat, atunci se vor afişa toate numerele prime din interval.

Date de intrare
De pe prima linie a fişierului de intrare prim.in se vor citi două numere n şi k, despărţite printr-un spaţiu, cu semnificaţia:

n este marginea superioară a intervalului din care se determină numerele prime
k are semnificaţia din enunţ.
Date de ieşire
În fişierul de ieşire prim.out se vor afişa pe prima şi singura linie cele 2*k sau 2*k-1 numere cerute, separate prin spaţiu.

Restricţii
1 ≤ n ≤ 10000
1 ≤ k ≤ 30
k ≤ n
Exemple
prim.in prim.out
21 2 5 7 11 13
18 2 5 7 11
18 18 2 3 5 7 11 13 17
100 7 17 19 23 29 31 37 41 43 47 53 59 61 67

Answer 1

#include <fstream>
using namespace std;
ifstream f("prim.in");
ofstream g("prim.out");
int n,k,nrnp,prim[10001]; //prim[i]=0 daca i este prim (la inceput presupunem ca toate-s prime)int main()
{
    f>>n>>k;
    for(int i=2;i<=n;++i)
        if(prim[i]==0) // i este prim => multiplii pana la n vor fi unu
            for(int j=2;j*i<=n;++j)
                prim[i*j]=1;
    for(int i=2;i<=n;++i)
        if(prim[i]==0)
            ++nrnp;
    prim[0]=1,prim[1]=1;
    k*=2;
    if(nrnp%2)
        --k;
    int prima_poz=0;
    if(k>nrnp)
        k=n;
    else
        prima_poz=(nrnp-k)/2;
    g<<"NRNP= "<<nrnp<<" K= "<<k<<" PRIMA POZ= "<<prima_poz<<endl;
    for(int i=1,j=0;i<=n&&j<k;++i)
        if(!prim[i])
        {
            if(prima_poz)
                --prima_poz;
            else
                ++j,g<<i<<' ';
        }
    return 0;
}