数学算法

求质数

2024.7.29

埃式筛选法

public int[] pi(int n) {
    int []r = new int[n + 1];
    for (int i = 2; i <= n; ++ i) {
        if (r[i] == 0) {
            r[i] = r[i - 1] + 1;
            for (int j = i * i; j <= n; j += i) {
                r[j] = -1;
            }
        } else {
            r[i] = r[i - 1];
        }
    }
    return r;
}//O(loglog(n))

欧拉筛，线性筛

public int eura(int n) {
    boolean []is_prime = new boolean[n + 1]; 
    Arrays.fill(is_prime, true);
    List<Integer> primes = new ArrayList<>();//存储质数
    for (int i = 2; i <= n; ++ i) {
        if (is_prime[i]) {
            primes.add(i);
        }
        for (int p : primes) { //遍历质数列表
            if (p * i > n) break; //越界
            is_prime[i * p] = false; //标记合数
            if (i % p == 0) break; //只用到小于当前数i的最小因子的质数就退出
        }
    }
    return primes.size();
}//O(n)

快速幂

2024.9.14

public long pow(int x, int N) {
	long res = 1;
	long n = N; //小心N是负数最大值-2^31,下面取反就会溢出，所以转换为long
	if (n < 0) { //负数变号
		n = -n;
		x = 1 / x;
	}
	for (; n != 0; n /= 2) {
		if (n % 2 == 1) {
			res *= x;
		}
		x *= x;
	}
	return res;
}

最大公约数和最小公约数

2024.9.26

最大公约数，欧几里得算法

//Euclidean算法两个数的求最大公约数
public static int gcd(int a, int b) {
    while (b != 0) {
        int t = b;
        b = a % b;
        a = t;
    }
    return a;
}

最小公约数，遍历2到gcd，依次取模就行

//求四个很大的数的最小公约数
int g = gcd(gcd(gcd(a, b), c), d);
int res = -1;
for (int i = 2; i <= g; i ++) {
    if (a % i == 0 && b % i == 0 && c % i == 0) {
        res = i;
        break;
    }
}
System.out.println(res);

最小公倍数，等于
$$
(a * b) / gcd(a, b);
$$