数学问题—Greatest common divisor

Greatest common divisor

Problem

写一个程序，给定两个正整数，计算并打印出最大公约数。

Solution

• 最大公约数(greatest common divisor, gcd )就是两个或者多个非零整数的最大公因子，最大公因子就是能够同时整除这些非零整数的最大整数。

• 实现求解最大公约数的算法有很多，其中一个有效的算法就是欧几里得算法（Euclid’s

  algorithm），同时《九章算术》里面的更相减损术也可以求解。

• 根据欧几里得算法，可以使用递归的方式实现，也可以使用非递归的方式实现。Euclid’s algorithm 也称之为 辗转相除法：1. 当两个数相等时，其中任意一个就是它们的最大公约数，因为它们的余数为 0；2. 当两个数不相等时，用较大数除以较小数，当余数不为 0 时，这时使较小数作为被除数，余数作为除数，继续 2 的操作，直至余数为 0,也就是这两个数相等时，其中任一数为最大公约数。
• 在 C++ 17 标准中已经有实现好的函数 std::gcd() ，可以直接使用；需要包含头文件 <numeric>

Code

github link

gitee link

/**
 * @file    : main.cpp
 * @brief   : Greatest common divisor
 * @author  : Wei Li
 * @date    : 2021-05-07
*/

#include <iostream>
#include <numeric> // C++ 17 std::gcd()

// recursive function
unsigned int gcd(unsigned int const a, unsigned int const b)
{
  return b == 0 ? a : gcd(b, a % b);
}

// non-recursive function
// unsigned int gcd(unsigned int a, unsigned int b)
// {
//   while (b != 0)
//   {
//     unsigned int r = a % b;
//     a = b;
//     b = r;
//   }
//   return a;
// }

// In C++17 there is a constexpr function called gcd() in the header <numeric> 
// that computes the greatest common divisor of two numbers.
// https://en.cppreference.com/w/cpp/numeric/gcd

int main(int argc, char** argv)
{
  unsigned int a = 0;
  unsigned int b = 0;
  std::cout << "Please input two positive integers: ";
  std::cin >> a >> b;

  std::cout << gcd(a, b) << std::endl;
  // C++ 17 <numeric>
  std::cout << std::gcd(a, b) << std::endl;
  
  return 0;
}
           

CMakeLists.txt

cmake_minimum_required(VERSION 3.10.0)
project(problem_02)

add_executable(problem_02 main.cpp)
           

Results

mkdir build
cd build
cmake .. -G "MinGW Makefiles"
mingw32-make
./problem_02.exe

// or using g++ command
g++ -std=c++17 -o problem_02 main.cpp

// ------------------------------------------------
// TEST
// $ ./problem_02.exe 
// Please input two positive integers: 256 64
// 64
// 64

// $ ./problem_02.exe 
// Please input two positive integers: 33 278
// 1
// 1

// $ ./problem_02.exe 
// Please input two positive integers: 3 99
// 3
// 3
// ------------------------------------------------
           

Reference

• Book 《The Modern C++ Challenge》
• Github