欧拉函数
筛法求欧拉函数
欧拉定理
AcWing 873. 欧拉函数 原题链接
给定n个正整数aiai，请你求出每个数的欧拉函数。
欧拉函数的定义
1 ~ N 中与 N 互质的数的个数被称为欧拉函数，记为ϕ(N)ϕ(N)。 若在算数基本定理中，N=pa11pa22…pammN=p1a1p2a2…pmam，则： ϕ(N)ϕ(N) = N∗p1−1p1∗p2−1p2∗…∗pm−1pmN∗p1−1p1∗p2−1p2∗…∗pm−1pm
输入格式
第一行包含整数n。
接下来n行，每行包含一个正整数aiai。
输出格式
输出共n行，每行输出一个正整数aiai的欧拉函数。
数据范围
1≤n≤1001≤n≤100, 1≤ai≤2∗1091≤ai≤2∗109
输入样例：
3
3
6
8
输出样例：
2
2
4
public static int euler(int x) {
int res = x;
for (int i = 2; i <= x / i; i++) {
if (x % i == 0) {
res = res - res / i;
while (x % i == 0) {
x /= i;
}
}
}
if (x > 1) {
res = res - res / x;
}
return res;
}
AcWing 874. 筛法求欧拉函数 原题链接
给定一个正整数n，求1~n中每个数的欧拉函数之和。
输入格式
共一行，包含一个整数n。
输出格式
共一行，包含一个整数，表示1~n中每个数的欧拉函数之和。
数据范围
1≤n≤1061≤n≤106
输入样例：
6
输出样例：
12
static List<Integer> primes = new ArrayList<>();
static boolean[] st;
static int[] phi;
private static void euler(int x) {
phi[1] = 1;
for (int i = 2; i <= x; i++) {
if (!st[i]) {
primes.add(i);
phi[i] = i - 1;
}
for (int pj = 0; primes.get(pj) <= x / i; pj++) {
st[primes.get(pj) * i] = true;
if (i % primes.get(pj) == 0) {
phi[primes.get(pj) * i] = phi[i] * primes.get(pj);
break;
}else {
phi[primes.get(pj) * i] = phi[i] * (primes.get(pj) - 1);
}
}
}
}
public static void main(String[] args) {
int n = in.nextInt();
st = new boolean[n + 1];
phi = new int[n + 1];
euler(n);
long res = 0L;
for (int i = 1; i <= n; i++) {
res += phi[i];
}
out.println(res);
out.flush();
out.close();
}