题目: POJ1284

算法思路:

n的最小素因子小于等于根号n, 所以遍历1-根号n之间的数.
遇到因子就减去该因子的所有倍数.
因为所有倍数都减去了, 所以让n除以该因子, 直到除不尽.

代码

#include <stdio.h>

int Euler(int n){
    int res = n;
    for (int i = 2; i * i <= n; i++){
        if (n % i == 0){
            n /= i;
            res -= (res / i);
        }
        while (n % i == 0) n /= i;
    }
    if (n > 1) res -= res / n;
    return res;
}


int main(){
    int p; 
    while (scanf("%d", &p) != EOF){
        printf("%d\n", Euler(p - 1));
    }

    return 0;
}

复杂度分析

$O( \sqrt n )$.

参考

https://blog.csdn.net/qq_35975367/article/details/105403662