Prime Visits [codingblocks]

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 N 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

Explanation

PM Modi chooses countries with numbers 2,3,5 and 7 for the first testcase.For the second testcase , he chooses countries with numbers 11,13,17 and 19.

Java Code:

https://ide.geeksforgeeks.org/WsxT7tgUdp

To find big prime number use Algo: Sieve of Eratosthenes

import java.util.*;
public class Main {
    public static Scanner scan = new Scanner(System.in);
    public static void main(String[] args) {
        int testCases = scan.nextInt();
        while(testCases-- >0) {
            int head = scan.nextInt();
            int tail = scan.nextInt();

            int[] primeArr = primefillArray(tail);
            System.out.println(countPrimefillArrayInRange(primeArr, head, tail));
        }
    }

    public static int[] primefillArray(int lastNum) {
        //to make last number inclusive
        lastNum++;
        int[] primeArr = new int[lastNum];
        for(int i=2; i<lastNum; i++) {
            if (primeArr[i] == 0) {
                primeArr[i] = 1;
                for (int j=i+i; j<lastNum; j+=i) {
                    primeArr[j] = -1;
                }
            }
        }
        return primeArr;
    }

    public static int countPrimefillArrayInRange(int[] primeArr, int head, int tail) {
        int countPrime = 0;
        for (int i=head; i<tail; i++) {
            if (primeArr[i] == 1)
                countPrime++;
        }
        return countPrime;
    }
}