编程实现计算欧拉函数值的算法
时间: 2023-05-30 12:05:22 浏览: 83
欧拉函数是指小于或等于n的正整数中与n互质的数的个数,通常用φ(n)表示。
以下是一个Python代码实现欧拉函数的算法:
```python
def euler_phi(n):
result = n # 初始化结果为n
p = 2
while p * p <= n:
if n % p == 0:
while n % p == 0:
n //= p
result -= result // p
p += 1
if n > 1:
result -= result // n
return result
```
该算法的时间复杂度为O(sqrt(n)),其中p是n的因子。算法的思路是从2开始遍历n的因子,如果找到一个质因子p,则将p的倍数从结果中减去,直到n除以p的余数不为0为止。如果n最终不等于1,则说明n本身是一个质数,将n的贡献也从结果中减去。最终得到的结果就是n的欧拉函数值。
相关问题
编程实现计算欧拉函数值的算法C语言
#include <stdio.h>
int phi(int n) {
int result = n; // 初始化结果为 n
int i;
for (i = 2; i * i <= n; i++) {
if (n % i == 0) {
// i 是 n 的一个质因数
while (n % i == 0) {
// 除去所有 i 的因数
n /= i;
}
// 除去所有 i 的因数后,result 中要少了 i 的因数
result -= result / i;
}
}
if (n > 1) {
// n 是一个大于 sqrt(n) 的质数
result -= result / n;
}
return result;
}
int main() {
int n;
printf("请输入一个正整数 n:");
scanf("%d", &n);
printf("欧拉函数值为:%d\n", phi(n));
return 0;
}
用C语言编程实现计算欧拉函数值的算法
#include <stdio.h>
int euler(int n) {
int result = n;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
result = result / i * (i - 1);
while (n % i == 0) {
n /= i;
}
}
}
if (n > 1) {
result = result / n * (n - 1);
}
return result;
}
int main() {
int n;
printf("请输入一个正整数:");
scanf("%d", &n);
printf("欧拉函数值为:%d\n", euler(n));
return 0;
}
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)