什么是质数？

质数是大于1的自然数，除了1和它本身外，不能被其他自然数整除。

Java

class solution {
    public boolean isPrime(int n) {
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}

什么是最大公约数、最大公倍数？

参考: 【C语言】一篇博客带你弄懂最大公约数和最小公倍数

最大公约数（Greatest Common Divisor）GCD：

举个例子，比如12和16，12的约数有（1,2,3,4,6,12）, 16的约数有（1,2,4,8,16），公约数就是两个数共同的约数，比如这里的（1,2,4）, 那么最大公约数就是公约数里面最大的，就是这里的4.

最大公倍数（Leatest Common Multiple）LCM：

举个例子： 比如12和16, 我们将12 * 4 = 48, 16 * 3 = 48， 这是两个数第一次有倍数相等关系，就叫48是最小公倍数。

假设两个已知的数a和b，那么存在以下公式：

$$a * b = gcd(a,b) * lcm(a, b)$$

所以我们只需要求得最大公约数或者最大公倍数其中一个，就能知道另外一个。

求最大公约数有很多方法，下面介绍一下暴力解法和辗转相除法

暴力解法

求公约数，假设已知a和b，公约数为x， 那么有等式，a % x == 0 AND b % x == 0， 那么我们枚举min(a,b)到1 为i，判断a和b对i的余数是否都等于0来判断最大公约数。

辗转相除法

用大数除小数取余数，小数与余数变成新的一对，直到余数为0.

暴力解

public int gcd(int a, int b) {
    int tmp = a < b ? a : b;

    for (int i = tmp; i >= 1; i--) {
        if (a % i == 0 && b % i == 0) {
            return i;
        }
    }
    return 1;
}

辗转相除法

public static int gcd(int a, int b) {
    while (a != 0) {
        int t = a;
        a = b % a;
        b = t;
    }
    return b;

}

德摩根定理：

设A和B为两个命题，则德摩根定律可表述为：

$$¬(A∧B)=(¬A)∨(¬B) \\ ¬(A∨B)=(¬A)∧(¬B)$$

中文描述：

非“A与B”和“非A”或者“非B”是等价的；

非“A或B”和“非A”与“非B”是等价的。

Changelog

10/10/25, 3:04 PM

View All Changelog

• 1ee1e-feat(wiki): algo -on 10/10/25