质数,约数,欧拉函数

质数

---

试除法判定质数

时间复杂度：O(√n)

例题：

给定 n 个正整数 ai，判定每个数是否是质数。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一个正整数 ai。

输出格式

共 n 行，其中第 i 行输出第 i 个正整数 ai 是否为质数，是则输出 Yes，否则输出 No。

数据范围

1≤n≤100
1≤ai≤2^31^−1

输入样例：

2
2
6

输出样例：

Yes
No

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T -- > 0){
            int n = sc.nextInt();
            if (is_prime(n)) System.out.println("Yes");
            else System.out.println("No");
        }

        sc.close();
    }

    private static boolean is_prime(int x){
        if (x == 1) return false;

        for (int i = 2; i <= x / i ; i++) {
            if (x % i == 0) return false;
        }

        return true;
    }
}

---

试除法分解质因数

时间复杂度：O(√n)

例题：

给定 n 个正整数 ai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一个正整数 ai。

输出格式

对于每个正整数 ai，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。

每个正整数的质因数全部输出完毕后，输出一个空行。

数据范围

1≤n≤100
2≤ai≤2×10^9^

输入样例：

2
6
8

输出样例：

2 1
3 1

2 3

import java.util.Scanner;

public class Main {
    static int N = (int)5e4 + 10;
    static int primes[] = new int[N];
    static int minp[] = new int[N];
    static boolean st[] = new boolean[N];
    static int cnt;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        init(N - 1);
        int T = sc.nextInt();
        while (T -- > 0){
            int n = sc.nextInt();

            for (int i = 0; i < cnt; i++) {
                int p = primes[i];
                int s = 0;

                if (n % p == 0){
                    while (n % p == 0){
                        n /= p;
                        s ++;
                    }
                    System.out.println(p + " " + s);
                }
            }

            if (n > 1) System.out.println(n + " " + 1);

            System.out.println();
        }

        sc.close();

    }

    private static void init(int x){
        for (int i = 2; i <= x; i++) {
            if (!st[i]){
                primes[cnt ++] = i;
                minp[i] = i;
            }

            for (int j = 0; i * primes[j] <= x; j++) {
                st[i * primes[j]] = true;
                minp[i * primes[j]] = primes[j];
                if (i * primes[j] == 0) break;
            }
        }
    }
}

---

筛质数

---

例题：

给定一个正整数 n，请你求出 1∼n 中质数的个数。

输入格式

共一行，包含整数 n。

输出格式

共一行，包含一个整数，表示 1∼n 中质数的个数。

数据范围

1≤n≤10^6^

输入样例：

8

输出样例：

4

朴素筛

---

import java.util.Scanner;

public class Main {
    static int N = (int)1e6 + 10;
    static int primes[] = new int[N];
    static boolean st[] = new boolean[N];
    static int cnt;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        get_primes(n);
        System.out.println(cnt);

        sc.close();
    }

    private static void get_primes(int n){
        for (int i = 2; i <= n; i++) {
            if (st[i]) continue;
            primes[cnt ++] = i;
            for (int j = i + i; j <= n; j += i) {
                st[j] = true;
            }
        }
    }
}

---

埃式筛法

import java.util.Scanner;

public class Main {
    static int N = (int)1e6 + 10;
    static int primes[] = new int[N];
    static boolean st[] = new boolean[N];
    static int cnt;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        get_primes(n);
        System.out.println(cnt);

        sc.close();
    }

    private static void get_primes(int n){
        for (int i = 2; i <= n; i++) {
            if (!st[i]){
                primes[cnt ++] = i;
                for (int j = i; j <= n; j += i) {
                    st[j] = true;
                }
            }
        }
    }
}

---

欧拉筛

(线性筛法)

import java.util.Scanner;

public class Main {
    static int N = (int)1e6 + 10;
    static int primes[] = new int[N];
    static boolean st[] = new boolean[N];
    static int cnt;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        get_primes(n);
        System.out.println(cnt);

        sc.close();
    }

    private static void get_primes(int n){
        for (int i = 2; i <= n; i++) {
            if (!st[i]) primes[cnt ++] = i;
            for (int j = 0; primes[j] <= n / i; j++) {
                st[primes[j] * i] = true;
                if (i % primes[j] == 0) break;
            }
        }
    }
}

---

约数

---

例题：

给定n个正整数 ai，对于每个整数ai，请你按照从小到大的顺序输出它的所有约数。

输入格式

第一行，包含整数 n。

接下来n行，每行包含一个整数ai。

输出格式

输出共n行，其中第i行输出第i个整数ai的所有约数。

数据范围

1≤n≤100

2≤ai≤2*10^9^

输入样例：

2
6
8

输出样例：

1 2 3 6
1 2 4 8

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while (n -- > 0){
            int a = sc.nextInt();
            is_divisor(a);
        }

        sc.close();
    }

    private static void is_divisor(int n){
        List<Integer> list = new ArrayList<>();

        for (int i = 1; i <= Math.sqrt(n); i++) {
            if (n % i == 0){
                list.add(i);
                if (n / i != i) list.add(n / i);
            }
        }
        Collections.sort(list);

        for (Integer t : list) {
            System.out.print(t + " ");
        }

        System.out.println();
    }
}

---

约数和定理

例题：

给定 n 个正整数 ai，请你输出这些数的乘积的约数之和，答案对 10^9+7 取模。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一个整数 ai。

输出格式

输出一个整数，表示所给正整数的乘积的约数之和，答案需对 10^9+7取模。

数据范围

1≤n≤100
1≤ai≤2×10^9^

输入样例：

3
2
6
8

输出样例：

252

import java.util.HashMap;
import java.util.Scanner;

public class Main {
    static int mod = (int)1e9 + 7;
    static HashMap<Integer,Integer> map = new HashMap<>();
    static long res = 1;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while (n -- > 0){
            int a = sc.nextInt();
            getSum(a);
        }
        for (int a : map.keySet()) {
            long sum = 0;
            int K = map.get(a);

            for (int i = 0; i <= K; i++) {
                long pow = 1;
                int tmp = i;
                while (tmp -- > 0) pow = pow * a % mod;
                sum = (sum + pow) % mod;
            }
            res = res * sum % mod;
        }

        System.out.println(res);

        sc.close();
    }

    private static void getSum(int n){
        for (int i = 2; i <= Math.sqrt(n); i++) {
            while (n % i == 0){
                map.put(i,map.getOrDefault(i, 0) + 1);
                n /= i;
            }
        }
        if (n > 1){
            map.put(n, map.getOrDefault(n, 0) + 1);
        }
    }
}

---

约数个数定理

例题：

给定 n 个正整数 ai，请你输出这些数的乘积的约数个数，答案对 10^9+7 取模。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一个整数 ai。

输出格式

输出一个整数，表示所给正整数的乘积的约数个数，答案需对 10^9+7 取模。

数据范围

1≤n≤100
1≤ai≤2×10^9^

输入样例：

3
2
6
8

输出样例：

12

import java.util.HashMap;
import java.util.Scanner;

public class Main {
    static int mod = (int)1e9 + 7;
    static HashMap<Integer,Integer> map = new HashMap<>();
    static long res = 1;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while (n -- > 0){
            int a = sc.nextInt();
            getNum(a);
        }

        for (int t : map.values()) {
            res = (res * (t + 1) % mod);
        }

        System.out.println(res);

        sc.close();
    }

    private static void getNum(int n){
        for (int i = 2; i <= Math.sqrt(n); i++) {
            while (n % i == 0){
                map.put(i, map.getOrDefault(i, 0) + 1);
                n /= i;
            }
        }
        if (n > 1){
            map.put(n, map.getOrDefault(n, 0) + 1);
        }
    }
}

---

欧几里得算法

例题：

给定 n 对正整数 ai,bi，请你求出每对数的最大公约数。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一个整数对 ai,bi。

输出格式

输出共 n 行，每行输出一个整数对的最大公约数。

数据范围

1≤n≤10^5
1≤ai,bi≤2×10^9^

输入样例：

2
3 6
4 6

输出样例：

3
2

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T -- > 0){
            int a = sc.nextInt();
            int b = sc.nextInt();
            System.out.println(gcd(a,b));
        }

        sc.close();
    }

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

    private static int gcd2(int a,int b){
        while (b != 0){
            int rem = a % b;
            a = b;
            b = rem;
        }
        return a;
    }
}

---

欧拉函数

---

求解欧拉函数

例题：

给定 n 个正整数 ai，请你求出每个数的欧拉函数。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一个正整数 ai。

输出格式

输出共 n 行，每行输出一个正整数 ai 的欧拉函数。

数据范围

1≤n≤100
1≤ai≤2×10^9^

输入样例：

3
3
6
8

输出样例：

2
2
4

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T -- > 0){
            int v = sc.nextInt();
            System.out.println(phi(v));
        }

        sc.close();
    }

    private static int phi(int x){
        int res = x;

        for (int i = 2; i <= x / i; i++) {
            if (x % i == 0){
                res = res / i * (i - 1);
                while (x % i == 0) x /= i;
            }
        }

        if (x > 1) res = res / x * (x - 1);

        return res;
    }
}

---

线性筛法筛欧拉函数

例题：

给定一个正整数 n，求 1∼n 中每个数的欧拉函数之和。

输入格式

共一行，包含一个整数 n。

输出格式

共一行，包含一个整数，表示 1∼n 中每个数的欧拉函数之和。

数据范围

1≤n≤10^6^

输入样例：

6

输出样例：

12

import java.util.Scanner;

public class Main {
    static int N = (int)1e6 + 10;
    static int primes[] = new int[N];
    static int phi[] = new int[N];
    static boolean st[] = new boolean[N];
    static int cnt,n;
    static long res;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        get_phi(n);

        for (int i = 1; i <= n; i++) {
            res += phi[i];
        }

        System.out.println(res);

        sc.close();
    }

    private static void get_phi(int x){
        phi[1] = 1;
        for (int i = 2; i <= n; i++) {
            if (!st[i]){
                primes[cnt ++] = i;
                phi[i] = i - 1;
            }

            for (int j = 0; i * primes[j] <= x; j++) {
                int t = i * primes[j];
                st[t] = true;
                if (i % primes[j] == 0){
                    phi[t] = phi[i] * primes[j];
                    break;
                }

                phi[t] = phi[i] * (primes[j] - 1);
            }
        }
    }
}