正文
c语言计算n的欧拉函数,c语言欧拉法
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
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 == 0 x%i == 0) {
sum--;
break;
}
}
}
printf("%d\n", sum);
}
return 0;
}
没问题，结果是对的。
其中注意，1是和大于1的每个数互质的。你将sum置为a-1，然后i从2开始计算,刚好把1默认算进去了。因此结果是正确的。
相关问答
Q1: C语言算一个数欧拉函数，输入0结束
unsigned int ss(unsigned int a)
{
unsigned int i;
for(i=2;i*i=a;i++) {
if(a%i==0) break;
}
if(i*i=a) return 0;
else return 1;
}
这个判断素数的函数逻辑是：
i在2~根号a（a是外部传入的需要判断的正整数）之间循环递增1，
如果a能被i整除，则跳出循环，否则继续循环直至i大于根号a退出循环，
退出循环后，判断当前i值是否小于根号a，
小于等于根号a，则是中途退出，返回0（是合数）；
大于根号a，则是循环条件完成退出，返回1（是质数）。
函数ss( a)在函数unsigned int oula(unsigned int n)中调用
unsigned int oula(unsigned int n)
{
unsigned int f=n,p;
for(p=2;p=n;p++)
if(ss(p)(n%p==0)) f=f*(1-(1/p)); 调用处
return f;
}
输入100,000,000，要看编译器对unsigned int的定义，
如果编译器定义为2 byte，则范围是：0~2^16-1(62353)，此时100,000,000会溢出。
如果编译器定义为4 byte，则范围是：0~4294967295,大于100,000,000.此时可以输入，但因数据太大，计算完成要超过2分钟（用去年主流配置的x86电脑测试），输入10,000,000就感觉明显的时延，要约20秒才能输出结果。
测试截图如下图：
另，函数unsigned int oula(unsigned int n)需要改成：
unsigned int oula(unsigned int n)
{
unsigned int f=n,p;
for(p=2;p=n;p++)
if(ss(p)(n%p==0))
//f=f*(1-(1/p)); //修改小数部分丢失问题
f=f*(p-1)/p;
return f;
}
供参考。
Q2: 欧拉函数如何运算
在数论，对正整数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
即费马小定理。
Q3: 请帮忙用C++编一个计算欧拉函数的程序。谢谢！！
这个跑起来了.
#include stdlib.h
#include stdio.h
#define N 101
char b[N];
int i,j,t,a,phi[N]={0,1,1};
int main(){
for(i=2;iN;i++)if(!b[i])
for(j=2;i*jN;j++)b[i*j]=1;//筛素数
puts("N\tphi(N)");
for(i=2;iN;i++){
t=i;
a=1;
for(j=2;ji;j++)if(!b[j]t%j==0){//找质因数
t/=j;
a*=j-1;
}
if(a==1)a=t-1;
else a*=t;
phi[i]=a;
printf("%d\t%d\n",i,a);
}
return 0;
}
Q4: 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;
}
直接复制的百度百科的，没具体看是什么功能
