首页 > 代码库 > 看破欧拉函数的奥秘
看破欧拉函数的奥秘
注意以下三个特殊性质
编程实现
利用欧拉函数和它本身不同质因数的关系,用筛法计算出某个范围内所有数的欧拉函数值。
1 //直接求解欧拉函数 2 #include<cstdio> 3 int euler(int n){ //返回euler(n) 4 int res=n,a=n; 5 for(int i=2;i*i<=a;i++){//从小到大尝试n的质因数 6 if(a%i==0){//如果i是n的质因数 7 res=res/i*(i-1);//提了一个1/i出来,先进行除法是为了防止中间数据的溢出 8 while(a%i==0) a/=i;//欧拉函数只记算一种质因数 9 } 10 } 11 if(a>1) res=res/a*(a-1);//如果最后还剩因子 12 return res; 13 } 14 int main(){ 15 int x; 16 scanf("%d",&x); 17 printf("%d",euler(x)); 18 return 0; 19 }
1 //筛选法打欧拉函数表 2 #include<cstdio> 3 #define Max 1000001 4 int euler[Max]; 5 void Init(){ 6 euler[1]=1; 7 for(int i=2;i<Max;i++) 8 euler[i]=i; 9 for(int i=2;i<Max;i++) 10 if(euler[i]==i)//如果i是质数 11 for(int j=i;j<Max;j+=i) 12 euler[j]=euler[j]/i*(i-1);//提一个1/i,先进行除法是为了防止中间数据的溢出 13 return ; 14 } 15 int main() 16 { 17 Init(); 18 for(int i=1;i<=100;i++) 19 printf("%d\n",euler[i]); 20 return 0; 21 }
看破欧拉函数的奥秘
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。