Program to find GCD

[takando12]

Here's a program i wrote to find the greatest common divisor of two numbers. I was required by the teacher to use for loops.
The output screen displayed "Enter two numbers:" and I entered 45 and 15 expecting an answer of 15 but I got "gcd is 225". Can someone please tell me what's wrong with the program?

void main()

int A[30],B[30],m,n,i,j,x,z,k,l,gcd=1;

cout<< "enter two numbers";
cin>>m>>n;
for(i=1,j=0;i<=m && j<30;i++)
{
if(m%i==0)
{ A[j++]=i;
z=j;
}
}
for(i=1,j=0;i<=n && j<30;i++)
{
if(n%i==0)
{ B[j++]=i;
x=j;
}
}

for(k=z;k>=0;--k)
{
for(l=x;l>=0;--l)
{
if(A[k]==B[l])
{ gcd=gcd*A[k];
}
}
}
cout<<"gcd is"<<gcd;
}

[helios]

Euclid's algorithm needs a single loop, it doesn't use multiplication, and it only needs a single extra variable, certainly not arrays. So I don't know what you did there.

[takando12]

I created two arrays with loops to find the divisors of the numbers. Then I check the largest number of the first array with the other numbers of the second array , in case of matching it enters the if else and gets stored into gcd . And then it goes back to the outer loop and takes the next number of the first array and repeats the process.for an example like 45 and 15 the arrays should contain 1 3 5 15 45 and 1 3 5 15. The matching happens thrice so maybe I should put an exit function after the if?

[helios]

Just use Euclid's algorithm. There's really simple-to-understand pseudocode in the Wikipedia article: https://en.wikipedia.org/wiki/Euclidean_algorithm#Implementations
Finding the GDC for small numbers has been a solved problem for 2300 years.

This is massively inefficient in both time and space. Also, 30 divisors is nowhere near enough for even modestly large numbers. 2310 (the product of the first five primes) has 32 divisors. Even in the "list all common divisors and keep the largest" style of naïve algorithms, there are better ways to do this.

The problem in you code is that you're multiplying gdc by the matching array elements. This would only be appropriate if you were storing prime factors in the arrays, not divisors.

[JLBorges]

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

// https://en.wikipedia.org/wiki/Euclidean_algorithm
// https://en.wikipedia.org/wiki/Euclidean_algorithm#Implementations
unsigned int gcd_e( unsigned int a, unsigned int b ) { return b == 0 ? a : gcd_e( b, a%b ) ; }

unsigned int gcd_fp( unsigned int a, unsigned int b ) // find common divisors in parallel
{
    unsigned int gcd = 1 ;

    for( unsigned int i = 2 ; i<a && i<b ; ++i )
    {
        while( a%i==0 && b%i == 0 ) // if i is a common divisor
        {
           gcd *= i ;
           a /= i ;
           b /= i ;
        }
    }

    return gcd ;
}

// https://cal-linux.com/tutorials//vectors.html
std::vector<unsigned int> non_unique_prime_divisors_of( unsigned int n )
{
    std::vector<unsigned int> result ;

    for( unsigned int i = 2 ; i < n ; ++i )
    {
        while( n%i == 0 )
        {
           result.push_back(i) ;
           n /= i ;
        }
    }

    if( n != 1 ) result.push_back(n) ;
    return result ;
}

unsigned int gcd_f( unsigned int a, unsigned int b ) // find common divisors one by one
{
    const auto fa = non_unique_prime_divisors_of(a) ;
    const auto fb = non_unique_prime_divisors_of(b) ;

    // common non-unique prime divisors of a and b
    // http://en.cppreference.com/w/cpp/algorithm/set_intersection
    std::vector<unsigned int> common_divisors ;
    std::set_intersection( std::begin(fa), std::end(fa),
                           std::begin(fb), std::end(fb),
                           std::back_inserter(common_divisors) ) ;

    unsigned int gcd = 1 ;
    for( auto divisor : common_divisors ) gcd *= divisor ;
    return gcd ;
}

int main()
{
    std::cout << gcd_e( 315, 2310 ) << '\n'
              << gcd_fp( 315, 2310 ) << '\n'
              << gcd_f( 315, 2310 ) << '\n' ;
}

http://coliru.stacked-crooked.com/a/93611c2698b59fae