Easy Prime!

Limits: 1s, 256 MB

There are N numbers in an array. You will have Q queries. In each query, you can make 2 operations. These are:

This is a companion discussion topic for the original entry at https://toph.co/p/easy-prime

You need to figure out something more efficient.

I think this should help:

1 Like

What’s wrong with my code??

if the number of query operations is large your code can not pass this time because of time complexity N*N.To pass your code in time you should apply segmented Tree or Binary Index Tree(BIT).

can i do it by seive or segseive? Reply earlier kindly.

use sieve with some modifications!
like don’t save primes just make a bool array and just look upto sqrt(1e7) for primes but mark till 1e7 (though 5e6 works) !
(0.0s solution)

1 Like

CLE for Sieve of Eratosthenes solution (https://toph.co/s/648460).
@hjr265 Bhaiya, please increase the CPU limit for Python.

1 Like

Done. Give it a try now.

1 Like

I can see the changes. But I’m still getting CLE. My code’s taking 1s on the second case.