Guest User

Hackerearth Alphaprime problem

a guest
Jan 24th, 2016
51
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2. import java.io.*;
  3. class AlphaPrimes
  4. {
  5.     //DONT FORGET TO COMMIT AND PUSH TO GITHUB
  6.     static int MAX = (int)1e6 + 10;
  7.     static boolean isComposite[]  = isCompositeArray(MAX);
  8.     static int numOfAlphaPrimes[] = new int[MAX];
  9.     private static void preCalculate()
  10.     {
  11.         for(int i=1;i<=MAX-1;i++)
  12.         {
  13.             if(isAlphaPrime(i))
  14.                 numOfAlphaPrimes[i] = numOfAlphaPrimes[i-1] + 1;
  15.             else
  16.                 numOfAlphaPrimes[i] = numOfAlphaPrimes[i-1];
  17.         }
  18.     }
  19.     public static boolean[] isCompositeArray(int N)     //Sieve of Erathanoses
  20.     {
  21.         boolean num[] = new boolean[N+1];
  22.         num[1]=true;
  23.         num[0]=true;
  24.         int end = (int)Math.sqrt(N);
  25.         for(int i=2;i<=end;i++)
  26.         {
  27.             if(!num[i])        
  28.                 for(int j=i*i;j<num.length;j+=i)
  29.                     num[j] = true;         
  30.         }
  31.  
  32.         return num;
  33.     }
  34.     private static boolean isAlphaPrime(int n)
  35.     {      
  36.  
  37.         if(!isComposite[n])
  38.             return true;
  39.         else
  40.         {
  41.             while(true)
  42.             {
  43.                 if(n < 10)
  44.                 {
  45.                     return !isComposite[n];
  46.                 }
  47.                 else
  48.                 {
  49.                     n = Integer.parseInt(Integer.toString(n).substring(1));
  50.                     if(!isComposite[n])
  51.                         return true;
  52.                 }
  53.             }          
  54.         }
  55.  
  56.     }
  57.     private static void solve(FastScanner s1, FastWriter out)/* This is the actual solution */{
  58.         int t = s1.nextInt();
  59.         preCalculate();
  60.         //out.println(Arrays.toString(numOfAlphaPrimes));
  61.         while(t-->0)
  62.         {
  63.             int l =s1.nextInt();
  64.             int r = s1.nextInt();  
  65.                 out.println(numOfAlphaPrimes[r]-numOfAlphaPrimes[l-1]);
  66.         }
  67.     }
  68.  
  69.     /************************ TEMPLATE STARTS HERE ************************/
  70.  
  71.     public static void main(String []args) throws IOException {
  72.         FastScanner in  = new FastScanner(System.in);
  73.         FastWriter  out = new FastWriter(System.out);
  74.         solve(in, out);
  75.         in.close();
  76.         out.close();
  77.     }
  78.  
  79.     static class FastScanner{
  80.         public BufferedReader reader;
  81.         public StringTokenizer st;
  82.         public FastScanner(InputStream stream){
  83.             reader = new BufferedReader(new InputStreamReader(stream));
  84.             st = null;
  85.         }
  86.         public String next(){
  87.             while(st == null || !st.hasMoreTokens()){
  88.                 try{
  89.                     String line = reader.readLine();
  90.                     if(line == null) return null;
  91.                     st = new StringTokenizer(line);
  92.                 }catch (Exception e){
  93.                     throw (new RuntimeException());
  94.                 }
  95.             }
  96.             return st.nextToken();
  97.         }
  98.         public String nextLine(){
  99.             String str = null;
  100.             try {
  101.                 str = reader.readLine();
  102.             } catch (IOException e) {
  103.                 e.printStackTrace();
  104.             }
  105.             return str;
  106.         }
  107.         public int nextInt(){
  108.             return Integer.parseInt(next());
  109.         }
  110.         public long nextLong(){
  111.             return Long.parseLong(next());
  112.         }
  113.         public double nextDouble(){
  114.             return Double.parseDouble(next());
  115.         }
  116.         int[] nextIntArray(int n) {
  117.             int[] arr = new int[n];
  118.             for (int i = 0; i < n; i++) {
  119.                 arr[i] = nextInt();
  120.             }
  121.             return arr;
  122.         }
  123.  
  124.         long[] nextLongArray(int n) {
  125.             long[] arr = new long[n];
  126.             for (int i = 0; i < n; i++) {
  127.                 arr[i] = nextLong();
  128.             }
  129.             return arr;
  130.         }
  131.         public void close(){   
  132.             try{ reader.close(); } catch(IOException e){e.printStackTrace();}
  133.         }
  134.     }
  135.     static class FastWriter{
  136.         BufferedWriter writer;
  137.         public FastWriter(OutputStream stream){
  138.             writer = new BufferedWriter(new OutputStreamWriter(stream));
  139.         }
  140.         public void print(int i) {
  141.             print(Integer.toString(i));
  142.         }
  143.         public void println(int i) {
  144.             print(Integer.toString(i));
  145.             print('\n');
  146.         }
  147.         public void print(long i) {
  148.             print(Long.toString(i));
  149.         }
  150.         public void println(long i) {
  151.             print(Long.toString(i));
  152.             print('\n');
  153.         }
  154.         public void print(double i) {
  155.             print(Double.toString(i));
  156.         }
  157.         public void print(boolean i) {
  158.             print(Boolean.toString(i));
  159.         }
  160.         public void print(char i) {
  161.             try{writer.write(i);} catch(IOException e){e.printStackTrace();}
  162.         }
  163.         public void print(String s){
  164.             try{writer.write(s);} catch(IOException e){e.printStackTrace();}
  165.         }
  166.         public void println(String s){
  167.             try{writer.write(s);writer.write('\n');} catch(IOException e){e.printStackTrace();}
  168.         }
  169.         public void println(){
  170.             try{writer.write('\n');} catch(IOException e){e.printStackTrace();}
  171.         }
  172.         public void print(int arr[])
  173.         {
  174.             for (int i = 0; i < arr.length; i++) {
  175.                 print(arr[i]);
  176.                 print(' ');
  177.             }
  178.         }
  179.         public void close(){
  180.             try{writer.close();} catch(IOException e){e.printStackTrace();}
  181.         }
  182.     }
  183.  
  184.     /************************ TEMPLATE ENDS HERE ************************/
  185. }
RAW Paste Data