Deepak and Primes- having runtime error for boundary value

#1

#include
#include
#define ll long long int
using namespace std;
//ll n = 100000000;
ll p[100000000]={0};
vector a;
void sieve(ll q){
p[0] = p[1] = 0;
p[2] = 1;
for(ll i=3;i<=100000000;i += 2){
p[i] = 1;
}

for(ll i=3;i<=100000000;i += 2){
if(p[i]){
for(ll j=ii; j<=100000000; j+=2i){
p[j] = 0;
}
}
}

for(ll i=2;i<=100000000;i++){
    if(p[i]){
        a.push_back(i);
    }
}
 cout<<a[q-1];

}

int main() {
long long int q;
cin>>q;

sieve(q);

}
https://ide.codingblocks.com/s/59086

Cannot pass last 2 testcase , Run time error for bundary condition.
Whats Wrong in my code?

#2

Hi,
you have to use bitwise sieve or use bitset. this is because when you change the range of n (as described in above point) you can not use your vector P (max size 10^8) so use bitwise sieve or simple bitset.

Note : 5,000,000 th prime number is 86,028,121. Thus you need to set the size of ā€œpā€ (in your code) to a number greater than 86,028,121

Correct Code : https://ide.codingblocks.com/s/58420 1

Hit like if you get it!!
Cheers Coding

1 Like