数论--欧拉函数phi

也就是说要求n的欧拉函数 需要求的n的所有质因数
由合数的哪一部分 我们知道有两种求质因数的方法
都可以得到一个单独的n的欧拉函数值
例如：

单独求解x的欧拉函数值
unsigned euler(unsigned x)
{
    unsigned i, res = x;    //  unsigned == unsigned int
    for (i = 2; i < (int)sqrt(x * 1.0) + 1; i++)
    {
        if (!(x % i))
        {
            res = res / i * (i - 1);
            while (!(x % i))
            {
                x /= i;     //  保证i一定是素数
            }
        }
    }
    if (x > 1)
    {
        res = res / x * (x - 1);
    }
    return res;
}

此外 我们还可以通过筛法来获得欧拉函数表

const int MAXN = 100;

int phi[MAXN + 2];

int main(int argc, const char * argv[])
{
    for (int i = 1; i <= MAXN; i++)
    {
        phi[i] = i;
    }
    for (int i = 2; i <= MAXN; i += 2)
    {
        phi[i] /= 2;
    }
    for (int i = 3; i <= MAXN; i += 2)
    {
        if (phi[i] == i)
        {
            for (int j = i; j <= MAXN; j += i)
            {
                phi[j] = phi[j] / i * (i - 1);
            }
        }
    }

    return 0;
}

最快捷简便的方法是使用线性筛
同时将素数表与欧拉函数表同时制成

/*
 *  同时得到欧拉函数和素数表
 */
const int MAXN = 1e7;

bool check[MAXN+10];
int phi[MAXN+10];
int prime[MAXN+10];
int tot;    //  素数个数

void phi_and_prime_table(int N)
{
    memset(check, false, sizeof(check));
    phi[1] = 1;
    tot = 0;
    for (int i = 2; i <= N; i++)
    {
        if (!check[i])
        {
            prime[tot++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; j < tot; j++)
        {
            if (i * prime[j] > N)
            {
                break;
            }
            check[i * prime[j]] = true;
            if (i % prime[j] == 0)
            {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            else
            {
                phi[i * prime[j]] = phi[i] * (prime[j] - 1);
            }
        }
    }
    return ;
}
int main()
{
    phi_and_prime_table(1000);
    for(int i=0;i<tot;i++)
    {
        cout<<i<<" "<<phi[i]<<" "<<prime[i]<<endl;
     } 
     return 0;
}