least_common_multiple.cpp File Reference

#include <cassert>
#include <iostream>

Include dependency graph for least_common_multiple.cpp:

Go to the source code of this file.

Functions
unsigned int	gcd (unsigned int x, unsigned int y)
unsigned int	lcm (unsigned int x, unsigned int y)
void	tests ()
int	main ()

Detailed Description

Copyright 2020

Author

tjgurwara99

A basic implementation of LCM function

Definition in file least_common_multiple.cpp.

Function Documentation

gcd()

unsigned int gcd	(	unsigned int	x,
		unsigned int	y )

Function for finding greatest common divisor of two numbers. @params two integers x and y whose gcd we want to find.

Returns

greatest common divisor of x and y.

Definition at line 16 of file least_common_multiple.cpp.

                                                 {
    if (x == 0) {
        return y;
    }
    if (y == 0) {
        return x;
    }
    if (x == y) {
        return x;
    }
    if (x > y) {
        // The following is valid because we have checked whether y == 0
 
        unsigned int temp = x / y;
        return gcd(y, x - temp * y);
    }
    // Again the following is valid because we have checked whether x == 0
 
    unsigned int temp = y / x;
    return gcd(x, y - temp * x);
}

lcm()

unsigned int lcm	(	unsigned int	x,
		unsigned int	y )

Function for finding the least common multiple of two numbers. @params integer x and y whose lcm we want to find.

Returns

lcm of x and y using the relation x * y = gcd(x, y) * lcm(x, y)

Definition at line 43 of file least_common_multiple.cpp.

                                                 {
  return x / gcd(x, y) * y;
}

main()

int main

(

void

)

Main function

Definition at line 78 of file least_common_multiple.cpp.

           {
    tests();
    return 0;
}

tests()

void tests

(

)

Function for testing the lcm() functions with some assert statements.

Definition at line 50 of file least_common_multiple.cpp.

             {
    // First test on lcm(5,10) == 10
    assert(((void)"LCM of 5 and 10 is 10 but lcm function gives a different "
                  "result.\n",
            lcm(5, 10) == 10));
    std::cout << "First assertion passes: LCM of 5 and 10 is " << lcm(5, 10)
              << std::endl;
 
    // Second test on lcm(2,3) == 6 as 2 and 3 are coprime (prime in fact)
    assert(((void)"LCM of 2 and 3 is 6 but lcm function gives a different "
                  "result.\n",
            lcm(2, 3) == 6));
    std::cout << "Second assertion passes: LCM of 2 and 3 is " << lcm(2, 3)
              << std::endl;
 
    // Testing an integer overflow.
    // The algorithm should work as long as the result fits into integer.
    assert(((void)"LCM of 987654321 and 987654321 is 987654321 but lcm function"
                  " gives a different result.\n",
            lcm(987654321, 987654321) == 987654321));
    std::cout << "Third assertion passes: LCM of 987654321 and 987654321 is "
              << lcm(987654321, 987654321)
              << std::endl;
}