Count Numbers in Range Geeks Solution

Count Numbers in Range Geeks Solution

  June 18, 2017    

---

Problem : Count Numbers in Range who has 3 divisors

Idea : Numbers which falls under this category are square of prime number in that range i.e. prime numbers in square root range (left - right) , this is done to reduce Time complexity.

Here we are using seive of erasthone method to find prime numbers


Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
 {
     public static int seive(int n)
     {
      boolean arr[]=new boolean[n+1];
   Arrays.fill(arr,true);  
   int count=0;
   for(int i=2;i<=n;i++)
   {
       if(arr[i])
       {
           for(int p=2*i;p<=n;p+=i)
           {
               arr[p]=false;
           }
       }
   }
   for(int i=2;i<=n;i++)
   if(arr[i])
   count++;
   return count;
     }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
   int count=0;
   int n=(int)Math.sqrt(ab.nextInt());
   int k=(int)Math.sqrt(ab.nextInt());
  
   System.out.println(seive(k)-seive(n));
}
}
}