fork(17) download
copy 
  1. // Created by akashbhalotia
  2. import java.io.*;
  3. import java.util.*;
  4. class C
  5. {
  6.     public static void main(String[] args) throws IOException
  7.     {
  8.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  9.  
  10.         int i,N,A,B,count,lo,hi,max,sqrt=(int)Math.sqrt(1000000000);
  11.         long square;
  12.  
  13.         HashMap<Integer,Integer> map=new HashMap<>();
  14.         ArrayList<Integer> arr=new ArrayList<>();
  15.         arr.add(1);
  16.         map.put(1,0);
  17.  
  18.         for(i=2;i<=sqrt;i++)
  19.         {
  20.             if(!map.containsKey(i))
  21.             {
  22.                 arr.add(i);
  23.                 map.put(i, 0);
  24.                 square=i;
  25.                 square*=square;
  26.                 count=1;
  27.  
  28.                 while(square<=1000000000)
  29.                 {
  30.                     map.put((int)square,count++);
  31.                     arr.add((int)square);
  32.                     square*=square;
  33.                 }
  34.             }
  35.         }
  36.  
  37.         Collections.sort(arr);
  38.         int a[]=new int[arr.size()];
  39.  
  40.         for(i=0;i<arr.size();i++)
  41.             a[i]=arr.get(i);
  42.  
  43.         int T=Integer.parseInt(br.readLine().trim());
  44.         StringBuilder sb=new StringBuilder();
  45.  
  46.         while(T-->0)
  47.         {
  48.             max=0;
  49.  
  50.             String s[]=br.readLine().trim().split(" ");
  51.             A=Integer.parseInt(s[0]);
  52.             B=Integer.parseInt(s[1]);
  53.  
  54.             lo=(int)Math.sqrt(A);
  55.             hi=(int)Math.sqrt(B);
  56.  
  57.             if(lo*lo<A)
  58.                 lo++;
  59.  
  60.             lo*=lo;
  61.             hi*=hi;
  62.  
  63.             lo=Arrays.binarySearch(a,lo);
  64.             hi=Arrays.binarySearch(a,hi);
  65.  
  66.             for(i=lo;i<=hi;i++)
  67.                 max=Math.max(max,map.get(a[i]));
  68.  
  69.             sb.append(max).append("\n");
  70.         }
  71.         System.out.println(sb);
  72.     }
  73. }
Success #stdin #stdout 0.16s 2184192KB
comments (?)
stdin
copy 
3
10 20
6000 7000
2 1000000000
stdout
copy 
2
3
4
https://ideone.com/Njlvre
language:
Java (HotSpot 12)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!