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

Header Extras

// struct pair

typedef struct mmm
{
   int a,b;
}pai;


//  (a^b)%c
lld mod_power(lld a, lld n, lld mod){

    // returns (a^n) % mod.
    // '%' represents modulus operation.

    lld y = 1;
    while(n){
        if(n & 1)
            y = (y * a) % mod;
        a = (a * a) % mod;
        n >>= 1;
    }
    return y;
}

//  inverse modulo

lld inverse(lld num){

    // returns the inverse of num w.r.t. (10^9 + 7).
    // uses the property a^(-1) mod p = a^(p-2) mod p.
    return mod_power(num, MOD - 2, MOD);
}

 sieve
bool p[10000000000];
int prime(int a)
{
   for(int i=2;i*i<=a;i++)
   {
       if(!p[i])
       for(int j=2;i*j<=a;j++)
           p[i*j]=1;
   }
}

prime1 spoj

PRIME1 (SPOJ)

in the prime1 question the , the click point was that the range in which we had to print all the prime number was very small in comparison to the overall range of numbers.. So what we did was we found out all the possible prime factor within that range that(10^9) that could be a prime divisor for any number within the overall range...
Now one possibility is that we will compute all the prime numbers present within (10^9) but that is allot of work in comparison to the computing only in given ranges

so we decided to opt for the latter and computed only those prime numbers which were asked for

since the range is 10^5 and over all constraint is 10^9
it would take 10^4 test cases to beat the second method and make the 1st method more effective

Code:

#include <stdio.h>
int main()
{

    unsigned long long a[31625],b[100005],d,e,f,i,j,t,m,n;
    long long c;
    for(i=0;i<100005;i++)
        b[i]=0;
    for(i=0;i<31625;++i)
        a[i]=0;
    for(i=2;i<179;i++)
        if(!a[i])
        for(j=2;j*i<31625;j++)
        a[i*j]=1;

  scanf("%llu",&t);
  while(t--)
  {
      scanf("%llu",&m);
      scanf("%llu",&n);
      for(i=2;i<31625 && i*i<n;i++)
      {     if(!a[i])
          for(j=(m/i)*i;j<=n;j+=i)
          { c=j-m;

          /*if(j==2 || j==3)
            continue;
          if(j==1)b[j]=1;*/

              if(c>=0 && c<100001 && j!=i){
                b[c]=1;
                //printf("%lld\n",c+m);
                }
          }
      }

      for(i=0;i<=n-m;i++)
        if(!b[i] && m+i!=1)
        printf("%lld\n",m+i);
          for(i=0;i<=n-m;i++)
            b[i]=0;

  }

}