title: All the numbers with exactly 8 divisors
body: <p>Given <code>n</code>, I need the number of numbers which have exactly 8 divisors.</p>
  
  <pre><code>24 = 1, 2, 3, 4, 6, 8, 12, 24
  </code></pre>
  
  <p>Below <code>100</code> there are 10 numbers which satisfy the above condition.</p>
  
  <p><code>24, 30, 40, 42, 54, 56, 66, 70, 78 and 88</code>.</p>
  
  <p>Given n, How many numbers satisfy the above condition below <code>n</code>.</p>
  
  <p><strong>The First Approach:</strong></p>
  
  <p>I used the prime factors approach.</p>
  
  <pre><code>x = p1^k1 * p2 ^k2 * p3^k3 ...
  n = (k1 + 1)(k2 + 1)(k3 + 1)...
  </code></pre>
  
  <p>This approach is a bit slow when dealing with large numbers.</p>
  
  <pre><code>int max = 1000000000;
  int count = 0;
  for(int i = 0; i &lt; max; ++i)
     if(check(i))count++;
  
  private static boolean check(int num) {
      int ans = 1;
      int count = 0;
      while (num % 2 == 0) {
          num /= 2;
          count++;
      }
      ans *= (count + 1);
      if (ans &gt; 8)
          return false;
      for (int i = 3; i * i &lt;= num; ++i) {
          count = 0;
          while (num % i == 0) {
              count++;
              num /= i;
          }
          ans *= (count + 1);
          if (ans &gt; 8)
              return false;
      }
      if (num != 1)
          ans *= 2;
      if (ans &gt; 8)
          return false;
      return ans == 8;
  }
  </code></pre>
  
  <p><strong>The second approach:</strong></p>
  
  <p>Sieve similar method, which marks all the multiples of a number and then check if the count is <code>8</code> or not.</p>
  
  <pre><code>static int max = 100000000;
  static int[] facs = new int[max];
  
  for (int i = 2; i &lt; max; ++i) {
      for (int j = i; j &lt; max; j += i) {
          facs[j]++;
      }
  }
  int count = 0;
  for (int i = 0; i &lt; max; ++i)
      if (facs[i] == 7)//1 is a factor of all number so check for count 7
          count++;
  System.out.println(count);
  </code></pre>
  
  <p>However this approach is a bit faster but this cannot be used for bigger numbers above <code>10^9</code>.</p>
  
  <p>How do I calculate the numbers which have exactly 8 divisors above <code>10^9</code>?</p>
  
  <p>Is there any trick that I'm missing? How can I improve this?</p>