title: InterviewStreet unfriendly numbers java
body: <p>For more information about this question, please look here: <a href="https://www.interviewstreet.com/challenges/dashboard/#problem/4f7272a8b9d15" rel="nofollow">https://www.interviewstreet.com/challenges/dashboard/#problem/4f7272a8b9d15</a></p>
  
  <p>There is one friendly number and N unfriendly numbers. We want to find how many numbers are there which exactly divide the friendly number, but does not divide any of the unfriendly numbers.</p>
  
  <p>Input Format:
  The first line of input contains two numbers N and K separated by spaces. N is the number of unfriendly numbers, K is the friendly number.
  The second line of input contains N space separated unfriendly numbers.</p>
  
  <p>Output Format:
  Output the answer in a single line.</p>
  
  <p>Constraints:</p>
  
  <pre><code>1 &lt;= N &lt;= 10^6
  
  1 &lt;= K &lt;= 10^13
  
  1 &lt;= unfriendly numbers &lt;= 10^18
  </code></pre>
  
  <p>Sample Input:</p>
  
  <pre><code>8 16
  
  2 5 7 4 3 8 3 18
  </code></pre>
  
  <p>Sample Output:</p>
  
  <pre><code>1
  </code></pre>
  
  <p>Explanation :
  Divisors of the given friendly number 16, are { 1, 2, 4, 8, 16 } and the unfriendly numbers are {2, 5, 7, 4, 3, 8, 3, 18}. Now 1 divides all unfriendly numbers, 2 divide 2, 4 divide 4, 8 divide 8 but 16 divides none of them. So only one number exists which divide the friendly number but does not divide any of the unfriendly numbers. So the answer is 1.   </p>
  
  <p>Many people asked this question but no perfect answer has been given. This is not a duplicate as others are closed, I got to ask this question</p>
  
  <p>I've used Sieve of Eratosthenes to refine unfriendly numbers(remove duplicates, remove unnecessary numbers like 2 &amp; 4 in the given example. numbers which divide 2 &amp; 4 also divide 8, so only 8 wud serve the purpose. After doing all these I removed primes) </p>
  
  <p>Here is my code</p>
  
  <pre><code>import java.io.*;
  import java.util.*;
  
  public class unfriendly {
  public static ArrayList&lt;Long&gt; refine_unfriendly(ArrayList&lt;Long&gt; uf){
      int n=uf.size();
      long x;
      for(int i=uf.size()-1;i&gt;=0;i--){
          x=uf.get(i);
          for(int j=uf.size()-1;j&gt;=0;j--){
              if(j==i)
                  continue;
              if(j!=i &amp;&amp; uf.get(j)%x==0){
                  x=uf.get(j);
                  uf.remove(i);
                  break;
              }
              else if(j!=i &amp;&amp; x%uf.get(j)==0){
                  uf.remove(j);
                  break;
              }
          }
      }
      return uf;
  }
  
  public static void print_output(long k,ArrayList&lt;Long&gt; uf){
      int n=uf.size(),count=0,i;
      long x,y;
      if(n==0)
          count++;
      for(x=2;x&lt;=Math.sqrt(k);x++){
          if(k%x==0){
              for(i=0;i&lt;n;i++){
                  if(uf.get(i)%x==0)
                      break;
              }
              if(i==n)
                  count++;
              if(k/x!=x){
                  y=k/x;
                  for(i=0;i&lt;n;i++){
                      if(uf.get(i)%y==0)
                          break;
                  }
                  if(i==n)
                      count++;
              }
          }
      }
      for(i=0;i&lt;n;i++){
          if(uf.get(i)%k==0)
              break;
      }
      if(i==n)
          count++;
      System.out.println(count);
  }
  public static void main(String[] args) throws Exception {
      Scanner in=new Scanner(System.in);
      int n=in.nextInt();
      long k=in.nextLong();
      ArrayList&lt;Long&gt; uf=new ArrayList&lt;Long&gt;();
      for(int i=0;i&lt;n;i++)
          uf.add(in.nextLong());
      uf=refine_unfriendly(uf);
      print_output(k,uf);
  }
  }
  </code></pre>
  
  <p>This solves only 1 test case out of 6. Rest are exceeding the time limit. The brute force method (without refining) solved 3 test cases. Someone please help. </p>
  
  <p>Thanks in advance</p>