UVA 10699 - Count the factors(cpp file)

Problem Type : Number Theory

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstring>
using namespace std;

long int  arr[10000];

vector<long>prime;


void sieve()
{
    long int N= 2000;
    long int k = N;
    for(long int i=3; i<=k; i+=2)
    {
        if(arr[i]==0)
        {
            for(long int j=i*i; j<=N; j+=2*i)
            {
                arr[j] = 1;
            }
        }
    }
    arr[1] = 1;
    for(long int i=4; i<=N; i+=2)
    {
        arr[i] = 1;
    }

    prime.push_back(2);
    for(long int i=3; i<=N; i+=2)
    {
        if(arr[i]==0)
            prime.push_back(i);
    }
}
long  factorial(long int n)
{
    long int j=1,i;
    long int k = prime.size();
    for(i=0; i<k && n!=1; i++)
    {
        if(n%prime[i]==0)
        {

            while(n%prime[i]==0)
            {

                n = n/prime[i];
                arr[j]= prime[i];
                j++;
            }
        }

    }
    if(n!=1)
    {
        arr[j]=n;
        j++;
    }
    return j;

}

int main()
{
    sieve();
    long int i,j,k,n,c,sum,s;
    while(scanf("%ld",&n)==1)
    {
        if(n==0)
            break;
        s=0;
        sum = factorial(n);
        for(i=1; i<sum; i++)
        {
            if(arr[0]!=0)
                s++;
            if(arr[i]==arr[i+1])
                continue;
            else
                s++;
        }
        printf("%ld : %ld\n",n,s);
        memset(arr,0,sizeof(arr));
    }


}