c语言互质欧拉函数 欧拉函数互质是什么意思

C语言中这么求欧拉函数的值有什么问题吗，题目如下。

#includestdio.h

创新互联是专业的桃城网站建设公司，桃城接单;提供成都网站制作、网站设计、外贸网站建设,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行桃城网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!

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 == 0  x%i == 0) {

sum--;

break;

}

}        

}

printf("%d\n", sum);

}

return 0;

}

没问题，结果是对的。

其中注意，1是和大于1的每个数互质的。你将sum置为a-1，然后i从2开始计算,刚好把1默认算进去了。因此结果是正确的。

C语言实现欧拉函数

int eular(int n)

{

int ret=1,i; //定义变量

for(i=2;i*i=n;i++) //从i=2开始循环，判定条件为i*i小于等于n，循环一次i增加1

if(n%i==0) //判定条件为n除以i的余数等于0

{

n/=i,ret*=i-1; //n=n/i，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;

}

直接复制的百度百科的，没具体看是什么功能

欧拉函数是什么

在数论，对正整数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

即费马小定理。

欧拉函数如何运算

在数论，对正整数n，欧拉函数math\varphi(n)/math是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler's totient function、φ函数、欧拉商数等。

例如math\varphi(8)=4/math，因为1,3,5,7均和8互质。

从欧拉函数引伸出来在环论方面的事实和拉格朗日定理构成了欧拉定理的证明。

[编辑]φ函数的值

math\varphi(1)=1/math（唯一和1互质的数就是1本身）。

若n是质数p的k次幂，math\varphi(n)=p^a-p^=(p-1)p^/math，因为除了p的倍数外，其他数都跟n互质。

欧拉函数是积性函数——若m,n互质，math\varphi(mn)=\varphi(m)\varphi(n)/math。证明：设A, B, C是跟m, n, mn互质的数的集，据中国剩余定理，mathA \times B/math和C可建立一一对应的关系。因此math\varphi(n)/math的值使用算术基本定理便知，

若mathn = \prod_{p\mid n} p^{\alpha_p}/math，

则math\varphi(n) = \prod_{p\mid n} p^{\alpha_p-1}(p-1) = n\prod_{p|n}\left(1-\frac\right)/math。

例如math\varphi(72)=\varphi(2^3\times3^2)=2^(2-1)\times3^(3-1)=2^2\times1\times3\times2=24/math

[编辑]与欧拉定理、费马小定理的关系

对任何两个互质的正整数a, m，mathm\ge2/math，有

matha^{\varphi(m)} \equiv 1 \pmod m/math

即欧拉定理

当m是质数p时，此式则为：

matha^ \equiv 1 \pmod p/math

即费马小定理。