Problem in Prime Visits

#1

The code is running for the given sample input, but while submitting on hacker blocks, one test case is not being passed and other one is showing time limit exceeded
Question
PRIME VISITS
PMO gives two random numbers a & b to the Prime Minister. PM Modi wants to visit all countries between a and b (inclusive) , However due to shortage of time he can’t visit each and every country , So PM Modi decides to visit only those countries,for which country number has two divisors. So your task is to find number of countries Mr. Modi will visit.

Input Format:
The first line contains N , no of test cases. The next lines contain two integers a and b denoting the range of country numbers.

Constraints:
a<=1000000 & b<=1000000.
N<=1000

Output Format:
Output contains N lines each containing an answer for the test case.

Sample Input:
2
1 10
11 20
Sample Output:
4
4
Code https://ide.codingblocks.com/s/116536

#2

For generating prime numbers use the optimized Sieve of Eratosthenes(as taught in course in the Number Theory Section) because the constraints are large. This will not give TLE.
The naive approach of checking a prime number will not work.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.