OpenJudge

6:欧拉Phi函数升级版

总时间限制:
1000ms
内存限制:
65536kB
描述

在数论中,对正整数n,phi(n)的值是"小于等于n的数中,与n互质的数的个数”,并且也是模n乘法群Zn*的规模。

可以用下面公式计算:phi(n)=n(1-1/p1)(1-1/p2)...(1-1/pm),其中p1,p2...pm为n的所有质因数。

输入
一个正整数n,n<=10^5
输出
一个整数,phi(1)+phi(2)+...+phi(n)的值
样例输入
20
样例输出
128
提示
1.结果可能很大
2.O(NlogN)才能过,借鉴Eratosthenes筛法
全局题号
13637
添加于
2017-03-13
提交次数
9
尝试人数
5
通过人数
4