数论
1.判断质数
注意i 的终止条件本来是 i < = s q r t ( n u m ) i<=sqrt(num)i<=sqrt(num),但是计算开方太慢了，所以用 i ∗ i < = n u m ，但是i ∗ i 容易爆int，所以最终改成 i < = n u m / i ，后面的其他
代码也会采用这种写法，希望不会搞晕。
public static boolean is_prime(int num) {
for (int i = 2; i <= num / i; i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
2.最大公约数
public static int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
3.最小公倍数
public static int lcm(int a, int b){
return a/gcd(a,b)*b;
}
public static int gcd(int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
4.质数筛
下面的两种方法可以得到 小于等于n 的所有质数。
要想一次性得到很多质数，那么就要使用质数筛法，质数筛法有很多方法，现在给出一种 埃及筛法。这种方法写起来比较简单，而且比较快，强烈推荐这种写法。时间复杂度是：O(nloglogn)
public static void getPrimes(int n) {
boolean[] is_prime = new boolean[n + 1];
Arrays.fill(is_prime, true);
for (int i = 2; i <= n / i; i++) {
if (is_prime[i]) {
for (int j = i * i; j <= n; j += i) {
is_prime[j] = false;
}
}
}
for (int i = 2; i <= n ; i++) {
if (is_prime[i]){
System.out.println(i);
}
}
}
还有一种筛法，是 欧拉筛法，这种方法也比较快,时间复杂度是O(n)。但是，对于我来说，我比较喜欢上面的埃及筛法，因为写起来比较简单而且计算也比较快，大家也可以根据自己的喜好自己选择。
public static void getPrimes(int n) {
boolean[] is_prime = new boolean[n + 1];
ArrayList<Integer> primes = new ArrayList<>();
Arrays.fill(is_prime, true);
for (int i = 2; i <= n; i++) {
if (is_prime[i]) {
primes.add(i);
}
for (int j = 0; i * primes.get(j) <= n; j++) {
is_prime[i * primes.get(j)] = false;
if (i % primes.get(j) == 0) break;
}
}
for (int i = 2; i < is_prime.length; i++) {
if (is_prime[i]) {
System.out.println(i);
}
}
}
5.区间质数筛
该方法可以得到区间[a,b]的所有质数。步骤如下：
1.求出小于 sqrt b 的所有质数。
2.根据上一步结果筛出区间 [a,b]的所有质数。
// 这是求出小于n的质数
public static ArrayList<Integer> prime(int n) {
boolean[] is_prime = new boolean[n + 1];
ArrayList<Integer> prime = new ArrayList<>();
Arrays.fill(is_prime, true);
for (int i = 2; i <= n / i; i++) {
if (is_prime[i]) {
for (int j = i * i; j <= n; j += i) {
is_prime[j] = false;
}
}
}
for (int i = 2; i <= n; i++) {
if (is_prime[i]) {
prime.add(i);
}
}
return prime;
}
//这是求区间[a,b]的质数
public static void prime(int a, int b) {
//1.首先求出小于sqrt(b)的所有质数
int n = (int) Math.sqrt(b) + 1;
ArrayList<Integer> prime = prime(n);
boolean[] is_prime = new boolean[b - a + 1];
Arrays.fill(is_prime, true);
for (int p : prime) {
for (int j = (int) Math.ceil((double) a / p) * p; j <= b; j += p) {
if (j != p) {
is_prime[j - a] = false;
}
}
}
int count = 0;
for (boolean value : is_prime) {
if (value) count++;
}
System.out.println(count);
}
6.欧拉函数
public static int f(int n) {
int res = n;
for (int i = 2; i <= n / i; i++) {
if (n % i == 0) {
res -= res / i;
while (n % i == 0) {
n /= i;
}
}
}
if (n > 1) {
res -= res / n;
}
return res;
}
7.区间欧拉函数
public static int[] oula(int n) {
int[] res = new int[n + 1];
for (int i = 0; i < res.length; i++) {
res[i] = i;
}
for (int i = 2; i <= n; i++) {
if (res[i] == i) {
for (int j = i; j <= n; j += i) {
res[j] -= res[j] / i;
}
}
}
return Arrays.copyOfRange(res, 1, n + 1);
}
8.计算所有约数个数
public static int count(int n) {
int result = 1;
for (int i = 2; i <= n / i; i++) {
if (n % i == 0) {
int count = 0;
while (n % i == 0) {
count++;
n /= i;
}
result *= count + 1;
}
}
//说明此时n为质数,乘以2表示1和本身
if (n > 1) {
result *= 2;
}
return result;
}
9.计算所有约束和
public static long getSum(int n) {
long result = 0L;
for (int i = 1; i <= n / i; i++) {
if (n % i == 0) {
result += i;
if (i * i != n) {
result += n / i;
}
}
}
return result;
}
10.计算质因子个数
public static void count(int n) {
int count = 0;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
count++;
while (n % i == 0) {
n /= i;
}
}
}
if (n > 1) {
count++;
}
System.out.println(count);
}
11.扩展欧几里得
public static int[] ex_gcd(int a, int b) {
if (b == 0) {
return new int[]{a, 1, 0};
} else {
int[] result = ex_gcd(b, a % b);
return new int[]{result[0], result[2], result[1] - (a / b) * result[2]};
}
}
12.快速幂
public static int quickPower(int a, int b) {
if (b == 1) return a;
int half = quickPower(a, b / 2);
if (b % 2 == 0) {
return half * half;
} else {
return half * half * a;
}
}
13.快速幂取模
public static int quickPowerMod(int a, int b, int c) {
if (b == 1) return a;
int half = quickPowerMod(a, b / 2, c) % c;
if (b % 2 == 0) {
return half * half;
} else {
return half * half * a;
}
}
14.欧拉定理
15.求a关于b的逆元
public static int quickPowerMod(int a, int b, int c) {
if (b == 1) return a;
int half = quickPowerMod(a, b / 2, c) % c;
if (b % 2 == 0) {
return half * half;
} else {
return half * half * a;
}
}
public static int f(int a, int b) {
return quickPowerMod(a, b-2, b);
}
public static int[] ex_gcd(int a, int b) {
if (b == 0) {
return new int[]{a, 1, 0};
} else {
int[] result = ex_gcd(b, a % b);
return new int[]{result[0], result[2], result[1] - (a / b) * result[2]};
}
}
public static int f(int a, int b) {
int[] result = ex_gcd(a, b);
if (result[1] < 0) {
return b + result[1];
} else {
return result[1];
}
}
16.中国剩余定理
