1028 - Trailing Zeroes (I)

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1028

Solution Idea : number of divisors

Solution :

#include<bits/stdc++.h>
#define ll long long
using namespace std;

bool status[1000009];

vector<ll int>prime;

void sieve()
{
    ll int n=1000000;
    ll int sq=sqrt(n);

    prime.push_back(2);

    for(int i=4;i<=n;i=i+2) status[i]=1;

    for(int i=3;i<=sq;i=i+2)
    {
        if(status[i]==0)
        {
                   for(int j=i*i;j<=n;j=j+i)
            {
                status[j]=1;
            }
        }
    }
    status[1]=1;
    status[0]=1;

    for(ll int i=3;i<=n;i=i+2)
    {
        if(status[i]==0)      prime.push_back(i);
    }
}

ll int nod(ll int n)
{
    ll int sq=sqrt(n);
    ll int res=1;

    for(int i=0;i<prime.size() && prime[i]<=sq;i++)
    {
        int cnt=1;
  int c=prime[i];
        while(n%prime[i]==0)
        {
            n=n/prime[i];
            cnt++;
        }
        sq=sqrt(n);

        res= res*(cnt);
    }
    if(n!=1)
    {
        res=res*2;
    }
    return res;
}

int main()
{
    sieve();
   ll int t,n,ans;
   scanf("%lld",&t);

   for(ll int ca=1;ca<=t;ca++)
   {
       scanf("%lld",&n);
       ans=nod(n);
       ans--;
       printf("Case %lld: %lld\n",ca,ans);
   }

}