title: Efficiently Counting Divisors of a Number in O(n^(1/3)) in c++
body: <p>I found an efficient algorithm to count divisors of a number in O(n^(1/3)) here: <a href="https://codeforces.com/blog/entry/22317" rel="nofollow noreferrer">https://codeforces.com/blog/entry/22317</a></p>
  
  <p>I've implemented the algorithm in the code below. But it doesn't work properly.</p>
  
  <pre><code>#include &lt;bits/stdc++.h&gt;
  using namespace std;
  
  #define ll long long
  #define pb push_back
  #define endl "\n"
  #define pi 2*acos(0)
  
  #define debug(s) cout &lt;&lt; #s &lt;&lt; " = " &lt;&lt; s &lt;&lt; endl
  #define all(v) (v).begin(), (v).end()
  #define mem(a, val) memset(a, val, sizeof a)
  
  vector&lt;int&gt; prime(10000000, 1); // array size is 10^7
  void sieve(ll n){
      prime[0]=prime[1]=0;
      for(ll i=2; i&lt;=sqrt(n); i++){
          if(prime[i]==1){
              for(ll j=2; i*j&lt;=n; j++) prime[i*j]=0;
          }
      }
  }
  bool isPrime(ll n){
      if(n&lt;2) return false;
      return prime[n];
  }
  
  vector&lt;int&gt; primeTable;
  ll numberOfDivisors(ll n){
      for(int i=0; i&lt;1000000; i++){
          if(prime[i]==1) primeTable.pb(i);
      }
      ll ans=1;
      for(int i=0; ; i++){
          if(primeTable[i]*primeTable[i]*primeTable[i]&gt;n) break;
          ll cnt=1;
          while(n%primeTable[i]==0){
              n=n/primeTable[i];
              cnt++;
          }
          ans*=cnt;
      }
      double sqn=sqrt(n);
      if(isPrime(n)) ans*=2;
      else if((sqn-floor(sqn))==0 and isPrime((ll)sqn)) ans*=3;
      else if(n!=1) ans*=4;
  
      return ans;
  }
  
  int main()
  {
      ios_base::sync_with_stdio(false);cin.tie(NULL);
      ll n;
      cin &gt;&gt; n;
      ll N=cbrt(n);
      sieve(N);
      cout &lt;&lt; numberOfDivisors(n) &lt;&lt; endl;
  
      return 0;
  }
  </code></pre>
  
  <p>i.e for 15 it returns 2(should be 4), for 100 it returns 6(should be 9), for 999 it returns 8(which is correct), but again for 9999 it returns 6(should be 12). I think something is wrong in between line 42 and 45. But I'm unable to find the bug. Please help me find the bug.</p>