-
Notifications
You must be signed in to change notification settings - Fork 0
/
P7_10001st_prime.cpp
60 lines (47 loc) · 1.43 KB
/
P7_10001st_prime.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
*
* Description:
* First line contains 'T' , the number of test cases. This is followed by 'T' lines each containing an integer N
*
* Problem: https://projecteuler.net/problem=7
* https://www.hackerrank.com/contests/projecteuler/challenges/euler007
*
*
*/
#include <iostream>
#include <cmath>
#include <vector>
#include <stdint.h>
using namespace std;
#define MAX_PRIME 1000010
/* buffer to compute primes using sieve of Eratosthenes
* Refer: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
*/
char numbuff[MAX_PRIME];
// vector constist of primes only
vector<uint64_t> primes;
int main(int argc , char ** argv){
int count=MAX_PRIME;
int c;
cin>> c;
// mark non primes as 1
for(int idx=2;idx < count ;idx++){
int tmp=count/idx;
for (int j=2; j<=tmp ;j++ ){
numbuff[j*idx]=1;
}
}
// extract prime and push them to primes vector
for(int idx=2;idx < count ;idx++) {
if(numbuff[idx] ==0)
{ primes.push_back(uint64_t(idx)); }
}
// Get Nth prime number
for(int idx =0 ;idx < c; idx ++ ){
int tmp;
cin>>tmp;
if(tmp < primes.size())
cout<<primes[tmp-1]<<endl;
}
return 0;
}