如何快速求出与n互素的数有多少个?
(注:x与n互素,说明x与n的大公约数为1)
但当n很大的时候,这个方法就不优了。可能有同学已经发现了,这个不就是欧拉函数的定义吗,所以今天我们从数学上来分析如何快速求解。
int euler_phi(int n) {
int m = sqrt(n + 0.5);
int ans = n;
for (int i = 2; i <= m; ++i) {
if (n == 1) break;
if (n % i == ) {
ans = ans / i * (i - 1);
while (n % i == ) n /= i;
}
}
if (n > 1) ans = ans / n * (n - 1);
return ans;
}
相关文章