算法-数论

1
2
3
4
5
6
7

static boolean isPrime(int n) {
    if (n < 2) return false;
    // i * i <= n 可能溢出
    for (int i = 2; i <= n / i; i++)
        if (n % i == 0) return false;
    return true;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// isNotPrime[i] 表示 i 是否不是质数
static boolean[] isNotPrime = new boolean[10000];

static void getPrime(int n) {
    // 判断 [1, n] 中每个数是否是质数
    for (int i = 2; i <= n; i++) {
        if (isNotPrime[i]) continue;
        for (int j = i; j <= n / i; j++)
            isNotPrime[i * j] = true;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

static List<List<Integer>> decomposition(int n) {
    // 质因数从小到大排序
    // factors[i][0] 表示第 i 个质因数
    // factors[i][1] 表示第 i 个质因数的数量
    List<List<Integer>> factors = new ArrayList<>();
    for (int i = 2; i <= n / i; i++) {
        if (n % i == 0) { // 质因数
            List<Integer> factor = new ArrayList<>();
            factor.add(i);
            int cnt = 0;
            while (n % i == 0) { // 计算质因数数量
                cnt++;
                n /= i;
            }
            factor.add(cnt);
            factors.add(factor);
        }
    }
    if (n > 1) { // 最后剩下的质因数
        List<Integer> factor = new ArrayList<>();
        factor.add(n);
        factor.add(1);
        factors.add(factor);
    }
    return factors;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

// 质因数从小到大排序
// factors[i][0] 表示第 i 个质因数
// factors[i][1] 表示第 i 个质因数的数量
int factors[100][2];
int n_factor = 0; // 不同质因数的数量

void decomposition(int n) {
    for (int i = 2; i <= n / i; i++) {
        if (n % i == 0) {
            factors[n_factor][0] = i;
            while (n % i == 0) {
                factors[n_factor][1]++;
                n /= i;
            }
            n_factor++;
        }
    }
    if (n > 1) {
        factors[n_factor][0] = n;
        factors[n_factor++][1] = 1;
    }
}

1
2
3
4
5
6
7

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

static int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

static double sqrt(double x) {
    if (x < 0) return Double.NaN;
    double threshold = 1e-15;
    double left = 0.0;
    double right = x;
    while (true) {
        double mid = (left + right) / 2;
        if (Math.abs(mid * mid - x) < threshold) return mid;
        else if (mid * mid > x) right = mid;
        else left = mid;
    }
}

1
2
3
4
5
6
7
8

static double sqrt(double x) {
    if (x < 0) return Double.NaN;
    double threshold = 1e-15;
    double x1 = x;
    while (Math.abs(x1 - x / x1) > threshold * x1)
        x1 = (x / x1 + x1) / 2;
    return x1;
}