素数分解

每一个数都可以分解成素数的乘积，例如 84 = 22 31 50 71 110 130 170 * …

整除

令 x = 2^m0 3^m1 5^m2 7^m3 11^m4 * …

令 y = 2^n0 3^n1 5^n2 7^n3 11^n4 * …

如果 x 整除 y（y mod x == 0），则对于所有 i，mi <= ni。

最大公约数最小公倍数

image-20201029152552697

计数质数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int countPrimes(int n) {
        boolean[] notPrimes = new boolean[n + 1];
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (notPrimes[i]) {
                continue;
            }
            count++;
            for (long j = (long) (i) * i; j < n; j += i) {
                notPrimes[(int) j] = true;
            }
        }
        return count;
    }
}

最大公约数

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

最小公倍数为两数的乘积除以最大公约数。

1
2
3
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

进制转换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public String convertToBase7(int num) {
        if (num == 0) {
            return "0";
        }
        StringBuffer stringBuffer = new StringBuffer();
        boolean isNegative = num < 0;
        if (isNegative) {
            num = -num;
        }
        while (num > 0) {
            stringBuffer.append(num % 7);
            num /= 7;
        }
        String rlt = stringBuffer.reverse().toString();
        return isNegative ? "-" + rlt : rlt;
    }
}
1
2
3
4
5
class Solution {
    public String convertToBase7(int num) {
        return Integer.toString(num, 7);
    }
}