【编程基础C++】素数判定、最小公倍数与最大公因数的实现方法

本文主要是介绍【编程基础C++】素数判定、最小公倍数与最大公因数的实现方法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

素数

素数 是指大于1的自然数，且只能被1和自身整除。例如，2、3、5和7都是素数。它们在数学中非常重要，因为任何大于1的自然数都可以唯一地表示为素数的乘积，这被称为素数分解。

法一

#include <iostream>
using namespace std;bool IsPrime(int n)
{if(n <= 1){cout << n << "不是素数" << endl; return false;}for (int i = 2; i < n; i++){if ((n % i) == 0){cout << n << "不是素数" << endl;return false;}}cout << n << "是素数" << endl;return true;
}

法二

#include <iostream>
#include <algorithm>
using namespace std;bool IsPrime(int n)
{if(n <= 1){return false;}for (int i = 2; i <sqrt(n); i++){if ((n % i) == 0){return false;}}return true;
}

---

最大公因数

最大公因数（GCD） 是指两个或多个整数的最大正整数因子，它们共同的因子中最大的一个。比如，24和36的最大公因数是12，因为12是24和36的所有公因数中最大的。常用的计算方法包括辗转相除法。

辗转相除法

// 辗转相除法求最大公因数
int gcd(int a, int b) {while (b != 0) {int temp = b;b = a % b;a = temp;}return a;
}

另一写法

int gcd(int a, int b) {return b == 0 ? a : gcd(b, a%b);
}

---

最小公倍数

最小公倍数（LCM） 是指两个或多个整数的最小正整数倍数。换句话说，它是能被这些整数整除的最小数。例如，对于数字4和6，它们的最小公倍数是12，因为12是4和6的所有倍数中最小的一个。

计算最小公倍数的一种常用方法是利用最大公因数（GCD）。公式如下：

其中，a 和 b 是要计算最小公倍数的两个数，GCD(a, b) 是它们的最大公因数。这个公式利用了最大公因数和最小公倍数之间的关系，使得计算过程更加高效。

直接枚举法

int lcm(int a, int b) {int multiple = std::max(a, b);while (true) {if (multiple % a == 0 && multiple % b == 0)return multiple;multiple++;}
}

根据GCD算LCM

// 计算最小公倍数
int lcm(int a, int b) {return (a * b) / gcd(a, b);
}

这篇关于【编程基础C++】素数判定、最小公倍数与最大公因数的实现方法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---