给你一个正整数,请问有多少个比n小的且与n互质的正整数,请你用C++实现
时间: 2024-02-20 15:02:07 浏览: 208
大整数类的C++源码实现
5星 · 资源好评率100%
好的,以下是一个使用C++实现欧拉函数的例子:
```c++
#include <iostream>
using namespace std;
int phi(int n) {
int result = n; // 初始化为n
int p = 2;
while (p * p <= n) {
if (n % p == 0) {
while (n % p == 0) {
n /= p;
}
result -= result / p;
}
p++;
}
if (n > 1) {
result -= result / n;
}
return result;
}
int main() {
int n;
cout << "请输入一个正整数n: ";
cin >> n;
cout << "比n小且与n互质的正整数的个数为:" << phi(n) << endl;
return 0;
}
```
输入一个正整数n,程序会输出比n小且与n互质的正整数的个数。
阅读全文