Prime Visiti Problem

#1

Out of 3 , 2 test cases passed but one test case is giving me timelimit error.Please help

#2

Hi @mikkyimran
Please share your code ide so that i can have a look.

#3

Here , is the link–> https://ide.codingblocks.com/s/164250

#4

Hi @mikkyimran
Your code is working fine for cases where n and m are small but for large value of m and n it will show TLE because for each number between n and m you are checking if its prime or not and which is increasing time complexity of your code.
I m sharing you the code which handles all the test cases have a look at it :

#5

Sir ! can you please explain the code given in the link.

#6

Hi @mikkyimran
In this problem we are creating a array prime in which if i is prime then we store primes[i]=1 else prime[i]=0.
Then starting from 0 to b we mark all numbers less than a and even numbers as prime[i]=0 as even numbers can never be prime except 2 and rest numbers as primes[i]=1 as they can or can not be prime.

    for (int i = 2; i <= b; i++){
        if((i&1)==0 || i<a){
            primes[i]=0;
        }else{
            primes[i]=1;
        }
    }

Then starting from i=3 to b we are marking all their multiples as not a prime.

for (int i = 3; i <=b; i+=2) {
int j=2;
while(i*j<=b){
primes[i*j]=0;
j++;
}
}

Then finding the count of prime numbers less than b.
int count=0;
for (int i = 0; i <=b; i++) {
if(primes[i]){
count++;
}
}