基本定义

不过一般写程序不用上面的求法，而是用下面的思路与代码

找出n的因子，剔除含有n的因子的数

代码模板

//求欧拉函数Φ(n)
int eulr(int n) {
    int ans = n;	//假设最初的结果就是有n个数，下面要一个一个从这n个数删
    // ans表示的是n的素因子个数
    // n表示的是素因子
    for(int i = 2; i * i <= n; i++) {	//循环结束条件是i * i <= 2，只用检查小于平方根的就行，否则就重复
        if(n % i == 0) {	//如果这个数是n的因数，就要从ans中删除掉所有i的小于n的倍数
            ans -= ans / i;	// ans / i表示比n小的i的最大倍数，这个倍数从1到ans/i一共有ans/i个，从ans中减去这么多
            while(n % i == 0) {		//从ans中删除i的倍数后，也要
                n  = n / i;		//这一个语句是为了保证完全消除我们刚才得到的那个i因子。防止重复减
            }
        }
    }
    if (n > 1) {	//若n大于1，则此时的n也是一个除1以外的因子
        ans -= ans / n;
    }
    return ans;
}

针对

1
2
3

while(n % i == 0) {		//从ans中删除i的倍数后，也要
    n  = n / i;		//这一个语句是为了保证完全消除我们刚才得到的那个i因子。防止重复减
}

和

1
2
3

if (n > 1) {	//若n大于1，则此时的n也是一个除1以外的因子
       ans -= ans / n;
}

举例说明

举一反三

题目一

题目二

题解

题目三

与上题几乎一样

线性筛法

参考文章