Wrong answer in DEEPAK AND PRIMES II

#1

Hi,

I am trying to solve using sieve_of_Eratosthenes method.

I am calculating from 0 - N numbers, then iterating from Start – End.

But I am not able to clear all the test cases in it. Please check.

Thanks.

#2

The purpose of the question is to teach you Segmented Sieve.

#3

But Segmented Sieve has same time complexity as Simple Sieve. Why code runs on TLE in some cases ?

#4

The essence of Segmented sieve is not for a better runtime complexity but to account for larger values of N. And there are other primality tests that perform better than this but they are randomised and for Competitive coding, you won’t need a better algorithm than Sieves for generating prime numbers and so it can’t give TLE if properly implemented.