欧拉函数

acwing: https://www.acwing.com/problem/content/875/

欧拉函数的值：1 到 \(n\) 中与 \(n\) 互质的数的个数。

求 \(x\) 的欧拉函数的值

LL phi(LL x){
	LL ans = x;
	for (LL i = 2; i <= x / i; i ++ ){
		if (x % i == 0){
			ans = ans / i * (i - 1);
			while (x % i == 0) x /= i;
		}
	}
	if (x > 1) ans = ans / x * (x - 1);
	return ans;
}

acwing：https://www.acwing.com/problem/content/876/

求 1 到 \(n\) 所有数的欧拉函数之和。

#include 
using namespace std;
#define LL long long
const int N = 1e6 + 10, M = 1e8 + 10;
LL n, phi[N], prime[N], cnt;
bool st[M];
LL get_eulers(LL n){
	st[1] = true;
	phi[1] = 1;
	for (int i = 2; i <= n; i ++ ){
		if (!st[i]){
			prime[++cnt] = i;
			phi[i] = i - 1;
		}
		for (int j = 1; j <= cnt && i * prime[j] <= n; j ++ ){
			st[i * prime[j]] = true;
			if (i % prime[j] == 0){
				phi[i * prime[j]] = phi[i] * prime[j];
				break;
			}
			phi[i * prime[j]] = phi[i] * (prime[j] - 1);
		}
	}
	LL ans = 0;
	for (int i = 1; i <= n; i ++ )
		ans += phi[i];
	return ans;
}
int main(){
	cin >> n;
	cout << get_eulers(n) << "\n";
	return 0;
}