欧拉函数

定义

欧拉函数（Euler's totient function），即 $\varphi(n)$，表示的是小于等于 n 和 n 互质的数的个数。

比如说 $\varphi(1)$ = 1。

当 n 是质数的时候，显然有 $\varphi(n)$ = n - 1。 性质： 1：欧拉函数是 积性函数。

即对任意满足 $\gcd(a, b)$ = 1 的整数 a,b，有 $\varphi(ab) = \varphi(a)\varphi(b)$。

特别地，当 n 是奇数时 $\varphi(2n) = \varphi(n)$。

证明参见 剩余系的复合。 2:若 n = p^k，其中 p 是质数，那么 $\varphi(n) = p^k - p^{k - 1}$。 （根据定义可知）

由唯一分解定理，设 $n = \prod_{i=1}^{s}p_i^{k_i}$，其中 p_i$ 是质数，有

$\varphi(n) = n \times \prod_{i = 1}^s{\dfrac{p_i - 1}{p_i}}$。

证明

$n = \sum_{d \mid n}{\varphi(d)}$。

实现

欧拉筛：

#include <bits/stdc++.h>
using namespace std;
bool IsPrime(int n){
    if(n<2)return false; //最小的素数是2，因此小于2的数字都是非素数。 
    if(n!=2 && n%2==0)return false;
	for(int i=2;i*i<=n;i++)//逐个判断【2，sqrt(n)】范围内有无其他因子
        if(n%i==0)return false;
    return true;
}
int main(){
	int n,ans=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		if(Isprime(i))ans++;
	}
	cout<<ans;
	return 0;
}