title: What is the highest power of A that divides N factorial?
body: <p>I am trying to solve this problem on codefights.com by finding out the largest prime factor and dividing the number with the powers of prime factor.</p>
  
  <pre><code>int highestPower(int N, int A) {
  int B =A, j=0,c=0, p=0,x;
  
  for(int i = 2; i&lt;=A; i++) {
      if( A%i == 0) {
          p = i&gt;p ? i:p;
          A/=i;
          --i;
      }
      if(i*i &gt; A &amp;&amp; B==A) {
          p = B;
          break;
      }
  }
  
  for(;(x = N/((int)Math.pow(p,++j))) &gt; 0; )
      c+=x;
  return c;
  </code></pre>
  
  <p>}</p>
  
  <pre><code>Input:
  
  0&lt;N&lt;10^9
  1&lt;A&lt;10^9
  </code></pre>
  
  <p>But this approach will fail for some test cases.One such test case is:</p>
  
  <pre><code>N:100
  A:1024
  Output:97
  Expected Output:9
  </code></pre>
  
  <p>Any suggestions on how to solve this problem?</p>