Question

4025 pbinfo

Cerința

Se dau K numere naturale nenule, mai mici sau egale cu 20222022. Pentru fiecare număr n dintre acestea, se cere aflarea celui de-al n-lea număr natural prim cu 2022.


Date de intrare

Programul citește de la tastatură numărul K, iar apoi K numere naturale, separate prin spații.


Date de ieșire

Programul va afișa pe ecran, pentru fiecare număr n dintre cele K numere date, al n-lea număr natural, prim cu 2022.


Restricții și precizări

1 ≤ K ≤ 2022

cele K numere citite vor fi mai mici sau egale cu 20222022




Exemplu

Intrare


3

4 23 198

Ieșire


11 67 595

Explicație

Şirul numerelor naturale, prime cu 2022, este format din numerele: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31,.

Answer 1

Răspuns:

#include <iostream>

#define N 100000000

using namespace std;

int K,i,n,x;

int caut(int l, int r)

{

int m = (l+r)/2;

int nr = m/2+m/3+m/337-m/6-m/674-m/1011+m/2022;

if(m-nr==n) return m;

if(m-nr<n) return caut(m+1,r);

return caut(l,m);

}

int main()

{

cin >> K;

for(i = 1; i <= K; i++)

{

cin >> n;

x = caut(1,N);

while((x%2==0)or(x%3==0)or(x%337==0))x--;

cout << x << " ";

}

return 0;

}