首页 > 代码库 > 【学习总结】数学-欧拉函数
【学习总结】数学-欧拉函数
定义
欧拉函数f(n)表示小于n并且与n互质的数的个数
f(n)=n(1?1p1)(1?1p2)…(1?1pk)(pi为n的质因子)
代码
C++ 单个处理int eulerPhi(int n) {
int m = (int)sqrt(n+0.5);
in ans = n;
for (int i = 2; i <= m; i++) {
if (n % i == 0) {
ans = ans / i * (i-1);
while (n%i==0)
n /= i;
}
}
if (n > 1)
ans = ans / n * (n - 1);
}
C++ 欧拉函数表void phiTable(int n, int* phi) {
for (int i = 2; i <= n; i++)
phi[i] = 0;
phi[1] = 1;
for (int i = 2; i <= n; i++) {
if (!phi[i]) {
for (int j = i*2; j <= n; j += i) {
if (!phi[j])
phi[j] = j;
phi[j] = phi[j] / i * (i - 1);
}
}
}
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。