2824 欧拉公式之打表算法

HDU 2824 The Euler function 欧拉φ函数：φ(n)是所有小于n的正整数里，和n互素的整数的个数。n是一个正整数。 欧拉证明了下面这个式子： 如果n的标准素因子分解式是p1^a1p2^a2……pm^am，其中众pj(j=1,2,……,m)都是素数，而且两两不等。则有 φ(n)=n(1-1/p1)(1-1/p2)……(1-1/pm) 如果n为奇素数，φ(n)=n-1. 解法：线性筛选法 在程序中利用欧拉函数如下性质，可以快速求出欧拉函数的值(a为N的质因素) (1) 若(N%a==0 && (N/a)%a==0) 则有:E(N)=E(N/a)a; (2) 若(N%a==0 && (N/a)%a!=0) 则有:E(N)=E(N/a)*(a-1);