(Relax 数论1.8)POJ 2478 Farey Sequence(欧拉函数:前n项欧拉数之和)

#include   
#include   
#include   
  
using namespace std;  
  
typedef long long ll;  
  
const int maxn = 1000015;  
  
bool u[maxn];//判断某一个数是否是素数  
ll su[maxn];//素数表  
ll num = 0;//素数的个数  
ll phi[maxn];//phi[i]前i项欧拉数之和  
  
  
void prepare() { //欧拉筛法产生素数表  
    ll i, j;  
    memset(u, true, sizeof(u));  
  
    for (i = 2; i <= 1000010; ++i) {  
        if (u[i]) {  
            su[++num] = i;  
        }  
  
        for (j = 1; j <= num; ++j) {  
            if (i * su[j] > 1000010) {  
                break;  
            }  
  
            u[i * su[j]] = false;  
  
            if (i % su[j] == 0) {  
                break;  
            }  
        }  
    }  
}  
  
void geteuler() {//phi[i]前i项欧拉数的和...单纯用欧拉函数的模板,而不采用性质进行优化的话,和可能会TLE  
    int i;  
    phi[1] = 1;  
    for (i = 1; i <= 1000000; i++) {  
        int j;  
        for (j = 1; j <= num && su[j] * i <= 1000000; j++) {  
            /** 
             * 在这里需要利用两个性质。 
             * 第一，大于1的质数x的欧拉函数值为x-1,1的欧拉函数值为1。 
             * 第二，若a为N的质因数，若(N % a == 0 && (N / a) % a == 0) 
             * 则有E(N)=E(N / a) * a； 
             * 若(N % a == 0 && (N / a) % a != 0) 
             * 则有：E(N) = E(N / a) * (a - 1)。 
             * 
             */  
            if (i % su[j] == 0) {  
                phi[su[j] * i] = su[j] * phi[i];  
                break;  
            } else {  
                phi[su[j] * i] = phi[i] * (su[j] - 1);  
            }  
        }  
    }  
    for (i = 3; i <= 1000000; i++)  
        phi[i] += phi[i - 1];  
}  
  
  
int main(){  
    prepare();  
    geteuler();  
  
    int n;  
    while(scanf("%d",&n)!=EOF,n){  
        printf("%lld\n",phi[n]);  
    }  
  
    return 0;  
}