Prime visits doubt

#1

getting tle with one test cases and other with wrong answer
please check my code , where i am doing mistake

#2

Hi @sk3657860
Wrong answer in the test case is due because you are using : ans2(prime upto b) - ans2(prime upto a) but its not correct . You must use : ans2(prime upto b-1) - ans1(prime upto a). And there is no need to use separate if - else for a=1 as this constraint is already tackled by ans2(prime upto b-1) - ans1(prime upto a). This change will give correct answer but 1 case will give time limit becz for each test case you are again and calculating prime number upto a and then b. Instead you should use Sieve of Eratosthenes to find all primes up to given limit. Then we compute a prefix array to store counts till every value before limit. Once we have prefix array, we can answer queries in O(1) time. We just need to return prefix[R] – prefix[L-1].

#3

for one test case it’s still giving TLE

#4
#5

Please share your correct code.

#6
#7

now its working , i dont know why the same code was giving TLE early

1 Like