欧拉函数及其相关性质的证明
函数 及其 相关 证明 性质 欧拉
2023-06-13 09:11:42 时间
欧拉函数定义
1∼N中与N 互质的数的个数被称为欧拉函数,记为ϕ(N)。
在算数基本定理中:
,则:
证明
设p1是 N的质因子,1∼N中p1的倍数有
,共
个。同理。若p2是N的质因子,1∼N中p2的倍数有
个。这
数中,其中既是p1的倍数,又是p2的倍数的数有N/(p1⋅p2)个。根据容斥原理,NNN中去掉p1和p2的倍数:
类似的,N的全部质因子都能使用容斥原理实现,得到与N互质的数的个数。
性质
证明性质1
若x为与n互质的数,则根据更相减损术原理,gcd(n,x)=gcd(n,n−x)=1。故,与n互质的x,n-x成对出现,总和为
性质1证毕。
证明性质2
算数基本定理中:
性质
若p是质数
证明性质3
因为p是质数,p与1∼p−1的每个数都互质,故
证明性质4
性质4证毕
证明性质5
性质5证毕
代码实现
质因数分解
int phi(int x){//求x的欧拉函数值
int ans=x;
for(int i=2;i*i<=x;i++){//分解x的质因数
if(x%i==0){
ans=ans/i*(i-1);
while(x%i==0){
x/=i;
}
}
}
if(x>1) ans=ans/x*(x-1);
return ans;
}
线性筛
int erla(int n){//利用线性筛更新欧拉函数值
int cnt=0;//质数个数
v[0]=v[1]=1;//标记0和1为非质数
phi[1]=1;//记录1的欧拉函数值为1
for(int i=2;i<=n;i++){//遍历2~n
if(!v[i]){//i是质数
prime[cnt++]=i;//存储i到质数表
phi[i]=i-1;//性质3: p是质数,phi(p)=p-1
}
//遍历质数表
for(int j=0;j<cnt&&prime[j]*i<=n;j++){
v[prime[j]*i]=1;//标记质数与i的乘积为非质数
if(i%prime[j]==0){//性质4:若p%i==0,phi(i*p)=p*phi(i)
phi[i*prime[j]]=prime[j]*phi[i];
break;
}else{//性质5:若p%i!=0,phi(i*p)=(p-1)*phi(i)
phi[i*prime[j]]=(prime[j]-1)*phi[i];
}
}
}
return cnt;//返回质数个数
}
Q.E.D.
相关文章
- 欧拉函数及其证明_欧拉函数证明题
- python 函数、运算符以及运算符优先级
- strftime函数
- 一文打通Lambda 表达式和函数式接口
- ES6 箭头函数解决 this 作用域问题
- 每日一题(2022-04-22)——旋转函数
- 深入解读PostgreSQL中的序列及其相关函数的用法
- 的应用MySQL中函数的使用及其优势(mysql中函数)
- SAP ALV demo—-自用(新显示函数,不用自定义GUI状态)详解编程语言
- Django的视图函数和路由系统中一些没有用过的小点详解编程语言
- fgets函数及其用法,C语言fgets函数详解
- MySQL及其 use函数的应用(mysqluse)
- 函数解析Linux atoi函数的功能(linuxatoi)
- Linux atoi函数及其使用方法(linuxatoi)
- 函数MySQL中的散列函数及其优势(mysql散列)
- MySQL分组平均函数,轻松计算数据平均值(mysql分组平均)
- Oracle值判断函数及其用法(oracle值判断)
- MySQL中实现条件判断if函数使用方法(mysql中if怎么写)
- 解析mysqlconnect函数及其用法(mysql_cnnect)
- Oracle中如何创建函数及其应用(oracle中创建函数吗)
- MSSQL汉字转拼音函数实现语句
- jstrim函数去空格函数与正则集锦
- AppBaseJs类库网上常用的javascript函数及其他js类库写的
- javascript获取当前日期时间及其它操作函数
- jQuery.extend函数的详细用法
- sql字符串函数大全和使用方法示例