求1~n中每个数的欧拉函数:

基于线性筛法

1.当数值为i且i为质数时， 其欧拉函数的值temp[i] 为 i - 1; (为1 ~ i - 1)

2.当 i % prim[j] == 0时， 

temp[i * prim[j]]  == temp[i] * prim[j];  //因为temp[i]中存在 i * (1 - 1 / p1) * (1 - 1 / p2) * ... * (1 - 1 / pj) (存在pj)
所以temp[i * prim[j]] == temp[i] * prim[j];

3.当 i % prim[j] != 0 时

temp[i * prim[j]] == temp[i] * prim[j] * (1 - 1 / prim[j]) == temp[i] * (prim[j] - 1);

代码实现：

    long long res = 0;

    temp[1] = 1;

    int cnt = 0;
    for(int i = 2 ; i <= n ; i++)
    {
        if(!choose[i])
        {
            choose[i] = 1;
            prim[cnt++] = i;
            temp[i] = i - 1;
        }
        for(int j = 0 ; prim[j] <= n / i ; j++)
        {
            choose[prim[j] * i] = 1;
            if(i % prim[j] == 0)
            {
                temp[i * prim[j]] = prim[j] * temp[i];
                break;
            }
            else
            {
                temp[i * prim[j]] = temp[i] * (prim[j] - 1);
            }
        }
    }

    for(int i = 1 ; i <= n ; i++)
    {
        res += temp[i];
    }