学步园

       水题，求欧拉函数单值。题意：给一个不超过10亿的数，算出不大于它且与它互素的正整数个数，就是求它的欧拉函数值。

       我的解题思路：没什么好说的，就是求欧拉函数单值，数据不多，不需要打欧拉函数表。

       我的解题代码：

#include <stdio.h>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>

using namespace std;

int Phi(int x);

int main()
{
    int x;
    while (~scanf("%d", &x))
    {
        if (x == 0) break;
        printf("%d\n", Phi(x));
    }
    return 0;
}

int Phi(int x)
{
    int ans = x;
    int cnt = (int)sqrt(x + 0.5) + 1;
    for (int i=2; i<cnt; ++i)
    {
        if (x % i == 0)
        {
            ans -= ans / i;
            while (x % i == 0) x /= i;
        }
    }
    if (x > 1) ans -= ans / x;
    return ans;
}