Greatest Common Factor and Lowest Common Multiple

 

Modules - Data Structures

 

Teacher’s Notes:

========================================================================

Finding the GCF and LCM of two numbers is a common process that is performed by students.  In this exercise, students will be challenged to break down the actual process they use to find these values.

 

Assignment:

========================================================================

 

The greatest common factor (GCF) of two numbers is the greatest number that is a factor of both numbers.  For instance, the numbers 12 and 16 have a GCF of 4 since 4 is the greatest number that both 12 and 16 can be divided into.

 

The lowest common multiple (LCM) of two numbers is the lowest number that has both numbers as factors.  For instance, the LCM of 4 and 6 is 12 since 12 /4 = 0 and 12 / 6 = 0;

 

Write a program that will input two integer numbers and then output (a) the GCF and (b) the LCM of the two numbers.

 

 

Solution (C++):

========================================================================

  
#include <iostream>
 
using namespace std;
 
int main()
{

    int factor1, factor2;
    cin >> factor1;
    cin >> factor2;
 
    //Finding the Greatest Common Factor

    int GCF  = 1;
    for(int x = 2; x <= factor1; x++)
        if( factor1 % x == 0 && factor2 % x == 0)
            GCF = x;
 
    cout << GCF << endl;
 
    //Finding Lowest Common Multiple

    int lowerFactor = factor1;
    if(factor2 < factor1)
        lowerFactor = factor2;
 
    //A cool way to write the above three lines of code
    //int lowerFactor = factor1<factor2?factor1:factor2;
 
    int LCM = lowerFactor;
    while(LCM % factor1!= 0 || LCM % factor2 != 0)
        LCM += lowerFactor;
 
    cout << LCM << endl;

    return 0;
}