Sunday, 18 January 2015

Counting total number of divisor (not just prime factors)

spoj question link 

solution link
http://spoj-solutions.blogspot.in/2014/10/comdiv-number-of-common-divisors.html

#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
bool p[1000009];
int prime(int a)
{int pe=sqrt(a);
   for(int i=2;i<=pe;i++)
   {
       if(!p[i])
       for(int j=2;i*j<=a;j++)
           p[i*j]=1;
   }
}


int main()
{
   //freopen("kr.in","r",stdin);
int t;

prime(1000005);
    int pi[100000];
    int kk=0;
    pi[kk++]=2;
    for(int i=3;i<1000000;i+=2)
    {
        if(!p[i])
            pi[kk++]=i;
    }
scanf("%d",&t);
while(t--)
{
    int a,b,c,d=1;
    scanf("%d %d",&a,&b);
    c=__gcd(a,b);
    /*for(int i=1;i<=c/2;i++)
    {
        if(c%i==0)
            d++;
    }*/
    if(c==1)
    {
    printf("1\n");
    continue;
    }

    int res=1;
    //printf("gcd is %d\n",c);
    for(int i=0;pi[i]<c && c;i++)
    {
        int co=1;
      // printf("pi %d %d\n",pi[i],c);
        while(c%pi[i]==0)
        {
            c/=pi[i];
            co++;
        }
        res*=co;
    }
    if(c>1)
        res*=2;
    printf("%d\n",res);
}
}


imp concept

to count the total number of divisor( not just prime) using the prime number for optimization , we calculate total number of times a prime divides the number and then multiply them.

for example in case of 12
the factors are , 1 ,2, 3,4,6,12              total of 6
the prime factors are 2 ( two times ) and 3 ( one time)
if we add one with the frequency and multiply them we get the total number of  factor( that are not just prime) :P