TLE for all test cases

#1

I’ve used a Bitset for sieve in the solution. Still its giving TLE for all test cases.

Could you please tell what I’m doing wrong here?

#2

Check now

#3

You can refer this https://ide.codingblocks.com/s/285203 implementation

#4

still getting the same TLE issue.

#5

Could you please tell me why are we incrementing j += (2 * i)

#6

Prime numbers are never even.
You know that i is odd.
j = i * i which is also odd.
j+=i will also give even values (as odd + odd =even). This is not required.
So j+=2 * i will also do

#7

thanks a lot. got it… in addition to this, I had to increase the size of the sieve array as well.

#8

earlier my sieve array size was 10^8, but when I increased this to 10^9, all test cases were passing. But it should’ve worked with 10^8 as well, right?

#9

It is given
Constraints

1<=n<=500000

So it may be that 500000th prime number of order > 10^8

#10

okay, thanks for the help. :slight_smile: