runtime error in ALGPRX

i’m getting runtime error(SIGSEV) in problem ALGPRX. Help me anyone. Here is my code.

Upper bound for given input is U<10^6.
Assign memory outside main(global scope).

int prime[1000006];

int main()


//insert code here

return 0;


Since U<10^6, you have to assign memory outside main…Even then your code will not get accepted because ,it is too slow…for every test case ,you are calculating all the prime nos upto ‘U’ .You are actually repeating the work already done.

A more better approach would be ,

Declare bool array [10^6],long long int sum[10^6] outside main.

Now using sieve of erastotehenes algo or any other good primality testing algo…update the bool array.

If(i=prime)then bool[i]=true, else false.

Now update the sum array…sum[i]=Sum of all primes less than i.

Now for each test case you can easily read from the sum array and update the answer as sum.
This code time complexity would roughly be O(10^7+N),where N is the no of test cases, which will compile under the time limit easily…If you find this post helpful upvote and mark it as accepted answer…CHEERS HAPPY CODING :).

1 Like