Question

urgeent va rog
Se dă un număr x. Se cere să se afișeze al x-lea număr prim.

Date de intrare
Se citește la tastatură numărul x.

Date de ieșire
Programul va afișa pe ecran al x-lea număr prim.

Answer 1

Problema se poate rezolva cu precalculare. Se poate observa ca sunt aproximativ 1200 de numere prime printre primele 10000 de numere.

varianta 1) mai putin optimizata :
Am facut Ciurul lui Eratostene  pentru a precalcula toate numere prime pana la 10000.
Daca nu stii ce este Ciurul lui Eratostene, iti pot explica.

#include <iostream>
using namespace std;
 
bool v[10001];
 
int main() {
  for (int i = 2; i * i <= 100000; i++ )
  if ( v[i] == 0 ) // daca d este prim
    for (int j = i * i; j <= 10000; j = j + i ) // vom marca numerele din i in i
      v[j] = 1;
  int nr = 0, sol, x;
    cin >> x;
    for(int i = 2; i <= 10000; i++)
      if(v[i] == 0 && nr != x) {
        nr++;
        sol = i;
      }
    cout << sol;
    return 0;
}

varianta 2) :

Am facut Ciurul lui Eratostene optimizat pentru a precalcula toate numere prime pana la 10000.
O idee de optimizare ar fi sa nu mai luam in calcul numerele pare pentru ca stim ca singurul numar prim par e 2. Pentru a optimiza memoria am folosit bool deoarece vectorul poate sa ia doar doua valori : adevarat sau fals. Memoria se poate optimiza mai mult folosind bitset dar nu cred ca este nevoie avand in vedere faptul ca nu ai precizat nimic despre limita de memorie.


#include <iostream>
using namespace std;
bool v[10001];
int main() {
  for(int i = 4; i <= 10000; i = i + 2)
    v[i] = 1;
  for(int i = 3; i * i <= 10000; i = i + 2)
    if(v[i] == 0)
    for(int j = i * i; j <= 10000; j = j + i)
      v[j] = 1;
    int nr = 0, sol, x;
    cin >> x;
    for(int i = 2; i <= 10000; i++)
      if(v[i] == 0 && nr != x) {
        nr++;
        sol = i;
      }
    cout << sol;
    return 0;
}