Trailing zeros(I)

#include<bits/stdc++.h>
#define M 10000009
#define ll long long
#define pb push_back
using namespace std;
bool marked[M];
vector<int>primes;
void sieve(void)
{
    for(int i = 2; i <= M; i++)
        marked[i] = true;
    for(int i = 3; i * i <= M; i += 2)
    {
        if(marked[i])
        {
            for(int j = i * i; j <= M; j += i + i)
                marked[j] = false;
        }
    }
    primes.pb(2);
    for(int i = 3; i <= M; i += 2)
    {
        if(marked[i])
            primes.pb(i);
    }
}
ll divisor_count(ll n)
{
    int divisors = 1, cnt;
    for(int i = 0; primes[i] * primes[i] <= n; i++)
    {
        if(n % primes[i] == 0)
        {
            cnt = 1;
            while(n % primes[i] == 0)
            {
                n /= primes[i];
                cnt++;
            }
            divisors *= cnt;
        }
    }
    if(n > 1)
        divisors *= 2;
    return divisors;
}
int main(void)
{
    sieve();
    int t;
    ll n;
    cin >> t;
    for(int i = 1; i <= t; i++)
    {
        cin >> n;
        printf("Case %d: %lld\n", i, divisor_count(n)-1);
    }
    return 0;
}