Informatică, întrebare adresată de dianacoldea, 9 ani în urmă

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.

Restricții

0 < x < 1 001

Exemplu
Date de intrare: 4                        
Date de iesire:7
rezolvare in C++

Răspunsuri la întrebare

Răspuns de rossetta
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


#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;
}







dianacoldea: dar imi poti spune ce semnifica bool si sol?
rossetta: bool este un tip de date
rossetta: sol este o variabila de tip int in care retinem solutia
rossetta: valoarea unei variabile de tip bool poate sa fie adevarat sau fals
rossetta: pentru claritate, poti sa inlocuiesti bool cu int dar o sa consume mai multa memorie
dianacoldea: aaa am inteles multumesc
rossetta: cu placere
rossetta: in pacate nu prea merge o solutie mai frumoasa pentru ca x este mare
rossetta: daca nu iti este clara solutia, ma anunti si iti explic mai amanuntit
Alte întrebări interesante