UVa OJ Board

Kamarul Kawnayeen wrote:A better approach to solve this problem should be using prime divisor. If you can find that a number N = (a^x)*(b^y)*(c^z) where a, b, c are prime number then the number of divisor of N should be (x+1)*(y+1)*(Z+1).

If you have already solve 583 (prime factor) then it will be easier for you to solve this problem.

Code: Select all

int divisors (long int c) {

		long int s;
		int i, j, flag;
		int divisornum = 1;
		i = 0;
		flag = 0;

		for(j=0;j<k;j++)
		{
			factor[j] = 0;
		}

		k = 0;

		if(c<0)
		{
			c = - c;
		}

		s = sqrt(c);

		while((c>=prime[i] && prime[i]<=s) && c!=1) //prime is an array which hold the prime number
		{
			j = 0;
			while((c%prime[i])==0)
			{
				flag = 1;
				c = c/prime[i];
				j++;
			}

			if(flag==1)
			{
				factor[k] = j;    //save the power of a prime factor to another array
				k++;
			}
			flag = 0;
		
			i++;

		}
		if(c>1)
		{
			factor[k] = 1;
			k++;
		}

		for(j=0;j<k;j++)
		{
			divisornum = divisornum * (factor[j]+1);        //applying the process which I describe earlier
		}

		return divisornum;

}

first done the seive code and find out prime number upto 56000 (approximately). Then use this code for finding number of divisor.