锐客网

  1. 首页 > 生活百科 > it技术 > >

c语言互质欧拉函数 欧拉公式c语言

IT技术欧拉

C语言中这么求欧拉函数的值有什么问题吗 ， 题目如下 。#includestdio.h
int main() {
int sum,x,i,a;
while(scanf("%d", x)!=EOF) {
a=x;
sum=a-1;
while (x2){
x--;
for (i=2; i=x;i) {
if (a%i == 0x%i == 0) {
sum--;
break;
}
}
}
printf("%d\n", sum);
【c语言互质欧拉函数 欧拉公式c语言】}
return 0;
}
没问题，结果是对c语言互质欧拉函数的 。
其中注意，1是和大于1c语言互质欧拉函数的每个数互质的 。你将sum置为a-1，然后i从2开始计算,刚好把1默认算进去了 。因此结果是正确的 。
欧拉函数是什么在数论 ， 对正整数n ， 欧拉函数\varphi(n)是少于或等于n的数中与n互质的数的数目 。此函数以其首名研究者欧拉命名，它又称为Euler's totient function、φ函数、欧拉商数等 。
例如\varphi(8)=4，因为1,3,5,7均和8互质 。
从欧拉函数引伸出来在环论方面的事实和拉格朗日定理构成了欧拉定理的证明 。
[编辑]φ函数的值
\varphi(1)=1（唯一和1互质的数就是1本身） 。
若n是质数p的k次幂，\varphi(n)=p^a-p^=(p-1)p^，因为除了p的倍数外，其他数都跟n互质 。
欧拉函数是积性函数——若m,n互质，\varphi(mn)=\varphi(m)\varphi(n) 。证明：设A, B, C是跟m, n, mn互质的数的集，据中国剩余定理，A \times B和C可建立一一对应的关系 。因此\varphi(n)的值使用算术基本定理便知，
若n = \prod_{p\mid n} p^{\alpha_p}，
则\varphi(n) = \prod_{p\mid n} p^{\alpha_p-1}(p-1) = n\prod_{p|n}\left(1-\frac\right) 。
例如\varphi(72)=\varphi(2^3\times3^2)=2^(2-1)\times3^(3-1)=2^2\times1\times3\times2=24
[编辑]与欧拉定理、费马小定理的关系
对任何两个互质的正整数a, m，m\ge2 ， 有
a^{\varphi(m)} \equiv 1 \pmod m
即欧拉定理
当m是质数p时，此式则为：
a^ \equiv 1 \pmod p
即费马小定理 。
C语言求解欧拉函数和本原根#include stdio.h
int eulerFunc(int n, int* num_out) {
int i, j, cnt = 0;
num_out[cnt] = 1;
for (i = 2; i = n;i) {
for (j = 2; j = i;j) {
if (i % j == 0n % j == 0) {
break;
}
}
if (ji) {
num_out[cnt] = i;
}
}
return cnt;
}
int main(void) {
int n, num[10], y, i;
scanf("%d", n);
y = eulerFunc(n, num);
for (i = 0; iy;i) {
printf("%d ", num[i]);
}
printf("\n%d", y);
return 0;
}
C语言实现欧拉函数int eular(int n)
{
int ret=1,i;//定义变量
for(i=2;i*i=n;i)//从i=2开始循环c语言互质欧拉函数，判定条件为i*i小于等于nc语言互质欧拉函数，循环一次i增加1
if(n%i==0)//判定条件为n除以ic语言互质欧拉函数的余数等于0
{
n/=i,ret*=i-1;//n=n/ic语言互质欧拉函数，ret = ret*(i-1)
while(n%i==0)//当n除以i的余数等于0时执行下面的语句，否则跳过
n/=i,ret*=i;
}
if(n1)//如果n1执行下面语句，否则跳过
ret*=n-1;//ret = ret*(n-1)
return ret;
}
直接复制的百度百科的，没具体看是什么功能
关于c语言互质欧拉函数和欧拉公式c语言的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站 。

    推荐阅读


    上一篇：怎么删除mysql表格，如何删除mysql中的表

    下一篇：python计算儒略日的库，python 儒略日