本文共 2092 字，大约阅读时间需要 6 分钟。

• 微信搜索：编程笔记本
• 微信搜索：编程笔记本
• 微信搜索：编程笔记本
  点击上方蓝字关注我，我们一起学编程
  欢迎小伙伴们分享、转载、私信、赞赏

小伙伴儿们看完以后可不可以帮我点亮一下在看呀~

1 判断素数

要判断一个整数 num 是否为素数，有几种思路。

• (1) 把 num 被 2 ~ num-1 之间的每一个整数去除，如果都不能被整除，那么 num 就是一个素数。

在这种方法中，有很多非必要的计算。比如，当被除数超过 num 的一半时就不可能整除，所以改进如下。

• (2) 把 num 被 2 ~ num/2 之间的每一个整数去除，如果都不能被整除，那么 num 就是一个素数。

上面两种算法的参考代码如下所示：

bool isPrime1(int num){
       bool isprime = true;        for (int i = 2; i <= num - 1; ++i) {
           if (num % i == 0) {
               isprime = false;            break;        }    }        return isprime;}bool isPrime2(int num){
       bool isprime = true;        for (int i = 2; i <= num / 2; ++i) {
           if (num % i == 0) {
               isprime = false;            break;        }    }        return isprime;}

再来分析一下：其实 num 不必被 2 ~ num/2 之间的每一个整数去除，只需被 2 ~ sqrt(num) 之间的每一个整数去除就可以了。如果 m 不能被 2 ~ sqrt(num) 间任一整数整除，num 必定是素数。

原因：因为如果 num 能被 2 ~ num/2 之间任一整数整除，其二个因子必定有一个小于或等于 sqrt(num) ，另一个大于或等于 sqrt(num) 。因此只需判断 2 ~ sqrt(num) 区间的整除性即可。

参考代码：

bool isPrime3(int num){
       bool isprime = true;    int k = (int)sqrt((double)num);        for (int i = 2; i <= k; ++i) {
           if (num % i == 0) {
               isprime = false;            break;        }    }        return isprime;}

注：2021 乐鑫科技提前批的编程题就考到了素数的判断，若不采用第三种解法就会超时。

2. 最大公约数

求解两个整数 a、b 的最大公约数，除蛮力法外，有两种较好的方法。

• (1) 辗转相除法

① a % b == c

② 若 c = 0 ，则返回 b

③ 若 c ≠ 0 ，则 a = b, b = c ，转 ①

参考代码：

• 微信搜索：编程笔记本
• 微信搜索：编程笔记本
• 微信搜索：编程笔记本

int gcd1(int a, int b){
       int c = a % b;        while (c != 0) {
           a = b;        b = c;        c = a % b;    }        return b;}

• (2) 相减法

① 若 a = b ，则返回 a

② 若 a > b ，则 a = a - b ，转 ①

③ 若 a < b ，则 b = b - a ，转 ①

参考代码：

int gcd2(int a, int b){
       while (a != b) {
           if (a > b) {
               a -= b;        } else {
               b -= a;        }    }        return a;}

3 最小公倍数

最小公倍数 = 两整数的乘积 ÷ 最大公约数

重用最大公约数的代码，参考如下：

int lcm(int a, int b){
       int ma = a;    int mb = b;        while (a != b) {
           if (a > b) {
               a -= b;        } else {
               b -= a;        }    }        return ma * mb / a;}

• 微信搜索：编程笔记本
• 微信搜索：编程笔记本
• 微信搜索：编程笔记本