poj2407

题意：给出n，求欧拉函数，欧拉函数euler(n)表示小于等于n的与n互质的数的个数，在欧拉函数，认为如果两数最大公约数为1，则两数互质。所以，n与1也互质，且euler(1)=1。

分析：计算公式为：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有不重复的质因数，x是不为0的整数。

 
   
    #include 
    <
    iostream
    >
    
#include 
    <
    cstdio
    >
    
#include 
    <
    cstdlib
    >
    
#include 
    <
    cstring
    >
    
#include 
    <
    cmath
    >
    

    using
    namespace
     std;

unsigned euler(unsigned x)
{
    //
     就是公式
    

     unsigned i, res 
    =
     x;

    for
     (i 
    =
    2
    ; i 
    <
     (
    int
    ) sqrt(x 
    *
    1.0
    ) 
    +
    1
    ; i
    ++
    )

    if
     (x 
    %
     i 
    ==
    0
    )
 {
 res 
    =
     res 
    /
     i 
    *
     (i 
    -
    1
    );

    while
     (x 
    %
     i 
    ==
    0
    )
 x 
    /=
     i; 
    //
     保证i一定是素数
    

     }

    if
     (x 
    >
    1
    )
 res 
    =
     res 
    /
     x 
    *
     (x 
    -
    1
    );

    return
     res;
}


    int
     main()
{

    //
    freopen("t.txt", "r", stdin);
    

    int
     n;

    while
     (scanf(
    "
    %d
    "
    , 
    &
    n), n 
    !=
    0
    )
 {
 printf(
    "
    %d\n
    "
    , euler(n));
 }

    return
    0
    ;
}