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