May lunchtime problem

I watched the youtube video of codechef and found that I have similar logic for the solution but I am creating a vector for prime number separately and getting TLE I have invested so much time in the question so please tell what I am doing wrong.

you just need the count of total prime number from 2 to the given number, so instead of calculating it again and again use the prefix sum array that will give you the total prime number at a given index, and then the expression will simply be the answer = prefix[n] - prefix[n/2]+1.

1 Like