09 June, 2013

C Program To Find LCM & GCD Of Integers/Numbers.

LCM: Least Common Multiple.

In Arithmetic, The LCM: Least Common Multiple[Also Called As 'Lowest Common Multiple'] Of Two Integers a & b, Usually Denoted By LCM[a,b], Is The Smallest Positive Integer That Is Divisible By Both a & b. If Either a Or b Is '0' [Zero], LCM[a,b] Is '0' [Zero].

Overview

A Multiple Of A Number Is The Product Of That Number & An Integer. For Ex, 10 Is A Multiple Of 5 Because 5 x 2 = 10, So 10 Is Divisible By 5 & 2. Because 10 Is The Smallest Positive Integer That Is Divisible By Both 5 & 2, It Is The Least Common Multiple Of 5 & 2. By The Same Principle, 10 Is The Least Common Multiple Of -5 & 2 As Well.

Example

What Is The LCM Of 4 & 6?

Multiples Of 4 Are:
  
   4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, ...

and the multiples of 6 are:
  
   6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, ...

Common multiples of 4 and 6 are simply the numbers that are in both lists:

   12, 24, 36, 48, 60, 72, ....

So, from this list of the first few common multiples of the numbers 4 and 6, their least common multiple is 12.

Application

When adding, subtracting, or comparing vulgar fractions, it is useful to find the least common multiple of the
denominators, often called the lowest common denominator, because each of the fractions can be expressed as a
fraction with this denominator. For instance,

[2\21] + [1\6] = [4\42] + [7\42] = [11\42]

where the denominator 42 was used because it is the least common multiple of 21 and 6.

This Post Contains A C Program To Find LCM & GCD Of Integers/Numbers With Correct Source Code, Algorithm & Output. This Program Is Written, Compiled & Executed At Turbo C/C++3.0 Compiler & Will Help You To Understand The Concept Of 'Cascading Of Operators' & 'Functions' From C Language. It Is A Well-Structured Program With Proper Comments Which Provides Step-By-Step Description Of Various Features Of The Language In A Simple & Easy-To-Understand Way.

# Note : You Can Simply Copy-Paste The Following Program Or Code Into Compiler For Direct Result.


C Program To Find LCM & GCD Of Integers/Numbers.

/* Declaration Of Header Files */
# include <stdio.h>
# include <conio.h>
int gcd ( int , int );      // Function Declaration.
void lcm ( int , int );   // Function Declaration.

/* Start Of Main Program */
void main()
{

/* Declaration Of Variables */
   int a, b;
   clrscr();

/* Asking For The Input From User */
   printf(" \n Enter Two Nos : ");
   scanf("%d %d", &a, &b);
   if (  a  <  b  )
   {
      printf(" \n GCD Of %d & %d Is : %d",a, b, gcd (a , b));    // Function Call.
   }
   else
   {
      printf(" \n GCD Of %d & %d Is : %d",a, b, gcd (a , b));   // Function Call.
   }
   lcm (a , b);    // Function Call.
   getch();
   }
/* End Of Main Program */

   int gcd ( int c , int d )     // Function Definition.
   {
      int r;
      r = d % c;
      while ( r  !=  0  )
      {
         d = c;
         c = r;
         r = d % c;
      }
      return (c);
   }
void lcm ( int x , int y )     // Function Definition.
{
   int l;
   if ( x < y )
   {
     l = ( x * y ) / gcd ( x , y );
   }
   else
   {
     l = ( x * y ) / gcd ( y , x );
   }
   printf(" \n LCM Of %d & %d Is : %d", a, b, l);
}

GCD: Greatest Common Divisor

In mathematics, the GCD: Greatest Common Divisor[also known as the 'Greatest Common Factor (GCF)', or 'Highest Common Factor (HCF)'], of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 8 and 12 is 4.

Notation

In this article we will denote the greatest common divisor of two integers a and b as gcd(a,b). Some older textbooks use (a,b).

Example

The number 54 can be expressed as a product of two other integers in several different ways:

   54 x 1 = 27 x 2 = 18 x 3 = 9 x 6.

Thus the divisors of 54 are:

    1, 2, 3, 6, 9, 18, 27, 54.

Similarly the divisors of 24 are:

    1, 2, 3, 4, 6, 8, 12, 24.

The numbers that these two lists share in common are the common divisors of 54 and 24:

    1, 2, 3, 6.

The greatest of these is 6. That is the greatest common divisor of 54 and 24. One writes:

    gcd(54,24) = 6.

Reducing fractions

The greatest common divisor is useful for reducing fractions to be in lowest terms. For example, gcd(42, 56) = 14, therefore,

   {42\56} = {(3)(14) \ (4)(14)} = {3\4}.

Co-prime numbers

Two numbers are called relatively prime, or co-prime if their greatest common divisor equals 1. For example, 9 and 28 are relatively prime.




No comments:

Post a Comment

Subscribe To:

Most Commonly Asked Programs In 'C' & 'C++' Language.

Blog Archive