UVA 294 Divisors

At First  Check Out This Tutorial on  Finding Number Of Divisors


#include <bits/stdc++.h>
using namespace std;
#define n 1000005
bool a[n];
long long int k=1;
long long int twin[n];
void sieve()
{
    long long int i,j;
    a[0]=a[1]=1;
    for(i=4;i<=n;i=i+2)
    {
        a[i]=1;
    }
    for(i=3;i<=sqrt(n);i=i+2)
    {
        for(j=i*i;j<=n;j=j+2*i)
        {
            a[j]=1;        //3*3, 3*5,3*7.....
        }
    }
    for(i=2;i<=n;i++)
    {
        if(a[i]==0)
        {
           twin[k]=i;
           k++;
        }
    }

}


int main()
{
    long long int l,u,p,c,t,m,z,a,b,g,s,r,x,y;
    //freopen("294.txt","r",stdin);
    //freopen("294out.txt","w",stdout);
    cin>>t;
    sieve();
    for(x=1;x<=t;x++)
    {
        m=0;
        cin>>l>>u;
        for(p=l;p<=u;p++)
        {
           y=p;
           r=1;

           for(g=1;g<=k && twin[g]<=sqrt(y);g++)
           {
            c=0;
            if(y%twin[g]==0)
            {

            while(y%twin[g]==0)
            {
                c++;
                y=y/twin[g];
                if(y==0 || y==1)
                {
                    break;
                }

             }
              s=c+1;
              r=r*s;
            }



        }
        if(y!=1)
        {
            r=r*2;
        }
         if(r>m)
         {
            m=r;
            z=p;
         }


        //cout<<r<<endl;


        }
        printf("Between %lld and %lld, %lld has a maximum of %lld divisors.\n",l,u,z,m);

    }
    return 0;

}

Download Coding Interview Book and Get More Tutorials for Coding and Interview Solution: Click Here

Download System Design Interview Book and Get More Tutorials and Interview Solution: Click Here

Do you need more Guidance or Help? Then Book 1:1 Quick Call with Me: Click Here

Share on Google Plus

About Ashadullah Shawon

I am Ashadullah Shawon. I am a Software Engineer. I studied Computer Science and Engineering (CSE) at RUET. I Like To Share Knowledge. Learn More: Click Here