欧拉函数
欧拉函数
1944864971 发表于2年前
欧拉函数
  • 发表于 2年前
  • 阅读 0
  • 收藏 0
  • 点赞 0
  • 评论 0

新睿云服务器60天免费使用,快来体验!>>>   

 欧拉函数

 
 
 

给定一个数N;求1 到n-1与他互为质数的数的个数

 

欧拉函数可以求解

 

euler(n)=n*(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4),,,,,

 

P1 P2 P3 P4 。。。。。是n的质因数,

 

比如10的质因数有2 5

 

所以euler(10)=10*(1-1/2)*(1-1/5)=4

 

30的质因数 2 3 5

 

所以 结果是 8

 
8的质因数是2  所以结果是4(1 3 5 7)
 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
筛选法求欧拉函数
const int Max=51;
int euler[Max];
void Euler()
{
    euler[1]=1;
    for(int i=2;i<Max;i++)
        euler[i]=i;
    for(int i=2;i<Max;i++)
         if(euler[i]==i) //筛选掉不是质因数的i;
        for(int j=i;j<Max; j+=i) //保证j都是i的倍数,
        {
              euler[j]=euler[j]/i*(i-1);// 只要是i的倍数,j就不是质因子,那么euler[j]的值就会改变,不再等于j;
             cout<<"质因数含有 "<<i<<" 的数"<<j<<",其乘以(1-1/"<<i<<")后的结果是"<<euler[j]<<endl<<endl;
        }
 
}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
直接根据欧拉函数的定义
 
 
int euler(int n)
 {
     int a=n,res=n;
     for(int i=2; i*i<=a;i++) //一个数的质因数不会大于它的平方根
     {
         if(a%i==0) //保证i是质因数
            res=res/i*(i-1); //先乘后除防止溢出
         while(a%i==0)a/=i; //保证i是质因数
     }
     if(a>1)res=res/a*(a-1);
     return res;
 } 
 
 
 
 
 
 
 
 
 
  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 57
码字总数 0
×
1944864971
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: