O(sqrt(n)) 求phi(n)

2018-11-06 21:08:18


注意,不是打表,而是只求phi(n)

我们可以直接利用性质:$phi[n]=n*(1-\frac{1}{p_1})*(1-\frac{1}{p_2})*(1-\frac{1}{p_3})……*(1-\frac{1}{p_k})$ pi为n的质因数

代码:

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int phi(int x)
{
    int res=x;
    for(int i=2;i<=x;i++)
    {
        if(x%i==0)
        {
            res=res/i*(i-1);
            while(x%i==0) x/=i;
        }
    }
    return res;
}
int main()
{
    int n;
    while(1)
    {
        scanf("%d",&n);
        if(!n) break;
        printf("%d\n",phi(n));
    }
    return 0;
}