作业帮 > 数学 > 作业

如何求1到n中有多少个数与n互质

来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/05/24 01:36:40
如何求1到n中有多少个数与n互质
欧拉函数
把n分解质因数=p1^(a1)*p2^(a2)……pn^(an)
则小于n且与n互质的数的个数
Φ=p1^(a1-1)*(p1-1)*p2^(a2-1)*(p2-1)……pn^(an-1)*(pn-1)