UVa problem solution 11827 - Maximum GCD

problem link:


Discuss: in this problem you can take input as string.then convert it to number and push into a vector. and then run a nested loop and send every pair in gcd function. you can euclid algorithm it is efficient to find gcd. and compare return value with previous one if it is greater than that then replace the maximum value.


try your self before see the code



#include<bits/stdc++.h>
using namespace std;
int gcd(int n1,int n2)
{
int r;
   while(n2!=0)
   {
       r=n1%n2;
       n1=n2;
       n2=r;
   }
  return n1;


}
int main()
{
    int n,m,i,j,gg,t;

    cin >>t;
    while(t--)
    {
         char str[105];
         vector<int>vec;
         scanf("\n");
         gets(str);
         n=strlen(str);
         for(i=0;i<n;i++)
         {

             if(str[i]>='0'&&str[i]<='9')
             {
                    int num=0;
                 while(str[i]>='0'&&str[i]<='9')
                 {
                   int r=str[i]-'0';
                 num=10*num+r;
                 i++;
                 }
                 vec.push_back(num);
             }
         }
         m=vec.size();
         int maxx=1;
         for(i=0;i<m-1;i++)
         {
             for(j=i+1;j<m;j++)
             {
                 gg=gcd(vec[i],vec[j]);
                if(gg>maxx)
                   maxx=gg;
             }
         }
         cout <<maxx<<endl;
    }
    return 0;
}