title: ADAPRIME spoj tle
body: <blockquote>
  <p><a href="http://www.spoj.com/problems/ADAPRIME/" rel="nofollow noreferrer">PROBLEM</a>. This is a problem from SPOJ problems section.</p>
  <p>As you might already know, Ada the Ladybug is a farmer. She grows many vegetables and trees and she wants to distinguish between them. For this purpose she bought a funny signs, which contains a few digits. The digits on the sign could be arbitrarily permuted (yet not added/removed). Ada likes <strong>prime numbers</strong> so she want the signs to be prime (and obviously distinct). <strong>Can you find the number of signs with prime number which could be obtained?</strong></p>
  </blockquote>
  <p><strong>NOTE: Number can't have leading zero!</strong></p>
  <p><strong>Input</strong><br />
  <code>The first line of input will contain 1 ≤ T ≤ 10000, the number of test-cases.</code></p>
  <p><code>The next T lines will contain 1 ≤ D ≤ 9, the number of digits on sign, followed by D digits 0 ≤ di ≤ 9</code></p>
  <p><strong>Output</strong><br />
  <code>For each test-case, output the number of distinct primes which could be generated on given sign.</code></p>
  <p><strong>Example Input</strong><br />
  5<br />
  1 9<br />
  3 1 2 3<br />
  5 1 2 0 8 9<br />
  7 1 0 6 5 7 8 2<br />
  5 1 2 7 3 1</p>
  <p><strong>Example Output</strong><br />
  0<br />
  0<br />
  11<br />
  283<br />
  15</p>
  <p><strong>APPROACH</strong></p>
  <blockquote>
  <p>For each input, I am first finding all the primes upto 9999999999. For each test case, I first sort the array whose max size can be 9. After sorting, I iteratively find the next permutation, and check if its prime or not(which i have done already, so it takes a constant time now). But I am getting TLE. I have no idea where can i optimize my code.</p>
  </blockquote>
  <p><strong>CODE</strong></p>
  <pre><code>import java.io.BufferedReader;
  import java.io.InputStreamReader;
  import java.io.IOException;
  import java.util.Arrays;
  import java.util.HashSet;
  
  public class Main
  {
      public static int maxSize = (int)Math.pow(10,9);
      public static boolean[] isPrime = new boolean[maxSize];
      public static int count = 0;
      public static void main(String[] args) throws IOException
      {
          //find all the primes till maxSize - 1
          preProcess();
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          int t = Integer.parseInt(br.readLine());
          while(t &gt; 0)
          {
              String[] strArr = br.readLine().split(&quot; &quot;);
              int n = Integer.parseInt(strArr[0]);
              int[] arr = new int[n];
              for(int i = 0 ; i &lt; n ; i++)
              {
                  arr[i] = Integer.parseInt(strArr[i + 1]);
              }
              count = 0;
              HashSet&lt;Integer&gt; set = new HashSet&lt;&gt;();
              func(arr,0,n,set);
              System.out.println(count);
              t--;
           } 
           
      }
      public static void func(int[] arr,int pos,int n,HashSet&lt;Integer&gt; set)
      {
          Arrays.sort(arr);
          while(true)
          {
              //ignoring the leading zeroes cases.
              if(arr[0] != 0)
              {
                  //parses the int array and produces the number.
                  int val = parseInt(arr, n);
                  //System.out.println(&quot;val = &quot; + val);
                  if(isPrime[val] == true &amp;&amp; set.contains(val) == false)
                  {
                      //System.out.println(val);
                      count++;
                      set.add(val);
                  }
              }
              int i = n - 2;
              while(i &gt;= 0 &amp;&amp; arr[i] &gt;= arr[i + 1])
              {
                  i--;
              }
              if(i &lt; 0)
                  return;
              //finds the next greater number than arr[i]
              int index = findJustGreater(arr, i + 1, n - 1, arr[i]);
              swap(i,index,arr);
              reverse(arr, i + 1, n - 1);
              
          }
      }
      public static int findJustGreater(int[] arr,int l, int r,int key)
      {
          int low = l;
          int high = r;
          while(low &lt; high)
          {
              if(high == low + 1)
              {
                  if(arr[high] &gt; key)
                      return high;
                  else
                      return low;
              } 
              int mid = (low + high) / 2;
              if(arr[mid] &gt; key)
              {
                  low = mid;
              }
              else
              {
                  high = mid - 1;
              }
          }
          return low;
      }
  
      public static void reverse(int[] arr,int i,int j)
      {
          while(i &lt; j)
          {
              swap(i, j, arr);
              i++;
              j--;
          }
      }
  
  
      public static void swap(int i,int j,int[] arr)
      {
          int temp = arr[i];
          arr[i] = arr[j];
          arr[j] = temp;
      }
  
  
      public static int parseInt(int[] arr,int n)
      {
          int sum = 0;
          for(int i = 0 ; i &lt; n ; i++)
          {
              sum  = sum * 10 + arr[i];
          }
          return sum;
      }
  
      public static void preProcess()
      {
          for(int i = 0 ; i &lt; maxSize ; i++)
          {
              isPrime[i] = true;
          }
          for(int i = 4 ; i &lt; maxSize ; i += 2)
              isPrime[i] = false;
  
          int o = (int)Math.sqrt(maxSize) + 1;
          for(int i = 2 ; i &lt;= o ; i++)
          {
              if(isPrime[i] == true)
              {
                  for(int j = i * i ; j &lt; maxSize ; j += 2 * i )
                  {
                      isPrime[j] = false;
                  }
              }
          }
      }
  }
  </code></pre>
  <p><strong>THANKS FOR HELPING</strong></p>