欧拉函数模板

2018-06-17 23:46:33来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

转载 http://www.cnblogs.com/E-star/archive/2012/08/03/2621025.html

 

求欧拉函数的模板:

int euler(int n)//返回euler(n)
{
     int i;
     int res = n,a = n;
     for(i = 2;i*i <= a; ++i)
     {
         if(a%i == 0)
         {
             res -= res/i; //p(n) = (p - p/p1)(1 - 1/p2)......
             while(a%i == 0) a/=i;
         }
     }
     if(a > 1) res -= res/a;//存在大于sqrt(a)的质因子
     return res;
}

欧拉函数打表:

void SE()//select euler//类似于素数筛选法
{
    int i,j;
    euler[1] = 1;
    for(i = 2;i < Max; ++i)  euler[i]=i;
    for(i = 2;i < Max; ++i)
    {
         if(euler[i] == i)//这里出现的肯定是素数
         {
           for(j = i; j < Max; j += i)//然后更新含有它的数
           {
              euler[j] = euler[j]/i*(i - 1); // n*(1 - 1/p1)....*(1 - 1/pk).先除后乘
           }
        }
    }
     //for (int i = 1; i <= 20; ++i) printf("%d ",euler[i]);
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:关于Qt 报QDomDocument: No such file or directory错误解决办法

下一篇:qt--setWindowFlags各种标志位的窗口样式