欧拉函数

定义

---

欧拉函数

欧拉函数，记作φ(n)，表示的是在[1, n]中与n互质的数的个数。

性质

---

对于一个数n，如果n是质数，显然有φ(n)=n-1。
对于任意两个互质的整数a和b(即gcd(a,b) = 1)，有φ(ab) = φ(a)φ(b)。
φ(n) = n × ∏(1 - 1/p)（或φ(n) = n × ∏((p-1)/p）（p为n的所有质因数）。

求单个数的欧拉函数

int euler_phi(int n)  
{
    int result = n;
    for (int i = 2; i * i <= n; i++) 
	    if (n % i == 0)  
	    {
	        result = result / i * (i - 1);
	        while (n % i == 0) n /= i;
	    }
    if (n > 1) 
	    result = result / n * (n - 1);
    return ans;
}

求多个数的欧拉函数

constexpr int N = 1000000;
vector<int> primes;
bitset<N> is_not_prime;
int phi[N] = {0,1};
void eular_phi()
{
    for(int i=2;i<=N;i++)
    {
        if(!is_not_prime[i])
        {
	        primes.push_back(i);//不是素数则添加到primes中
	        phi[i] = i - 1;//并计算欧拉函数值
        }
        for(const int& prime:primes)//筛出从i*2到i*最后一个素数的合数
        {
            if(i*prime>N)
                break;//超出筛选范围就没有必要再筛了
            is_not_prime[i*prime]=true;//标记（合数=最小质因数*另一个数）为非素数
            if(i%prime==0)//若真则i=prime（最小质因数）*另一个数（大于等于prime）
            {
	            phi[i*prime] = phi[i] * prime;
	            break;//接下来的Prime都比现在的prime大，
                      //若继续循环则接下来的合数为（i*Prime=另一个数*Prime*prime）
                      //此数应在I=另一个数*Prime时被I*prime标记而不是现在
            }
			phi[i * prime] = phi[i] * phi[prime];
        }
    }
}