程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 歐拉函數模板,歐拉模板

歐拉函數模板,歐拉模板

編輯:C++入門知識

歐拉函數模板,歐拉模板


轉載 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]);
}

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved