Deepak & Primes II showing WA/TLE

#1

Question link - https://hack.codingblocks.com/contests/c/473/760
My Solution - https://ide.codingblocks.com/#/s/24359

I used segmented sieve. I pre-computed primes till sqrt(b) and then marked the multiples of these primes in range [a,b]. Some test cases are showing WA and TLE.
Please Check

#2

You need to precompute the primes upto the largest number and store it.Then check if each one is a prime by dividing by the list of primes generated earlier. ( 1 is not a prime :stuck_out_tongue: )
For reference, here’s the code

1 Like
#3

Can you explain this code -
for (p = primes.begin(); p != primes.end(); p++)
{

            if (*p >= cap) break;
            int start;
 
            if (*p >= m) start = (*p)*2;
            else start = m + ((*p - m % *p) % *p);
 
            for (int j = start; j <= n; j += *p) 
            {
                notprime.insert(j);
            }
}
#4

This loop is just to insert the multiples of the prime set (precomputed before) in a notprime set.
start = m + ((*p - m % *p) % *p) is just to ensure that multiples of *p to be inserted in notprime are greater than m. e.g. if m=13 and *p=3, start should be 13 + (3 - 13%3) = 15.

1 Like