欧拉公式求互质数个数C语言
时间: 2024-01-13 09:17:56 浏览: 83
以下是使用C语言实现欧拉函数求互质数个数的代码:
```c
#include <stdio.h>
#include <math.h>
int phi(int n) {
int ans = n;
for (int i = 2; i <= sqrt(n); i++) {
if (n % i == 0) {
ans = ans / i * (i - 1);
while (n % i == 0) {
n = n / i;
}
}
}
if (n > 1) ans = ans / n * (n - 1);
return ans;
}
int main() {
int t, n;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
printf("%d\n", phi(n));
}
return 0;
}
```
阅读全文