Acwing---873. 欧拉函数

本文主要是介绍Acwing---873. 欧拉函数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.题目

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

欧拉函数的定义

输入格式
第一行包含整数 $n$。

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

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

数据范围
$1\le n\le 100,$

$1\le ai\le 2\times 10^9$

输入样例：

3
3
6
8

输出样例：

2
2
4

2.基本思想

3.代码实现

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;public class _873欧拉函数 {private static int phi(int a) {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);return res;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();while (n-- > 0) {int x = sc.nextInt();System.out.println(phi(x));}}
}

这篇关于Acwing---873. 欧拉函数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---