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
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;
}
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?
Alte întrebări interesante
Limba română,
8 ani în urmă
Matematică,
8 ani în urmă
Matematică,
8 ani în urmă
Matematică,
9 ani în urmă
Matematică,
9 ani în urmă