1.对每个数分解质因数

2.

代码复现：

import java.io.*;

public class Main {

    static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {

        int n = Integer.parseInt(in.readLine());

        while (n -- > 0){

            int a = Integer.parseInt(in.readLine());

            int res = a;

            for (int i = 2; i <= a / i; i ++){

                if (a % i == 0){

                    res = res / i * (i - 1);

                    while (a % i == 0) a /= i;

                }

            }

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

            out.write(res+"");

            out.newLine();

        }

        out.flush();

    }

}