POJ 2407 Relatives(欧拉函数)

题目链接

题意 ： 求小于等于n中与n互质的数的个数。

思路 ： 看数学的时候有一部分是将欧拉函数的，虽然我没怎么看懂，但是模板我记得了，所以直接套了一下模板。

这里是欧拉函数的简介。

 #include <iostream>
 #include <cstdio>
 #include <cstdlib>
 #include <cstring>
 #include <cmath> using namespace std; int main()
 {
     int x;
     while (scanf("%d", &x) && x )
     {
         int  res = x;
         for (int i =; i < (int) sqrt(x *1.0) +; i++)
         {
             if (x % i ==)
             {
                 res = res / i * (i -);
                 while (x % i ==)
                     x /= i; // 保证i一定是素数
             }
         }
         if (x > )
             res = res / x * (x -);
         printf("%d\n", res);
     }
     return ;
 }