Getting gcd and lcm at the same time

        /// <summary>
        /// We can get both least common multiple and greatest common divisor
        /// at the same time. By using that m*u + n*v has constant value and at the start time
        /// m*u + n*v = 2*a*b and LCM(a, b) = a * b / GCD(a, b). If m = 0 or n = 0 then n is GCD
        /// or m is GCD, so we can get lcm by division v by 2 or u by 2;
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        private static int[] GetLCMandGCD(int a, int b)
        {
            int m = a;
            int n = b;
            int u = b;
            int v = a;
            int []result = new int[2];
            while(! ( (m == 0) || (n == 0) ) )
            {
                if (m >= n)
                {
                    m = m – n; v = v + u;
                }
                else
                {
                    n = n – m; u = u + v;
                }
            }
            if (m == 0)
            {
                result[0] = v / 2;
                result[1] = n;
            }
            else
            {
                result[0] = u /2;
                result[1] = m;
            }
            return result;
        }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s