求分母为n的最简真分数个数

Question

public class ProperFractions {
  public static long properFractions(long n) {
    if (n==1) return 0;
    long r=n;
    for(long d=2;d*d<=n;d++){
        if(n%d == 0){
            while(n%d == 0){
                n/=d;
            }
            r-=r/d;
          }
    }
    if(n>1) r-=r/n;
    return r;
  }
}

这段代码为什么可以求分母为n的最简真分数个数。

Answer 1

所谓最简真分数
首先它是真分数，分子不能比分母大
最简，不能简化，也就是分子不是分母的因子
不是因子就是不能整除
理解了题意再看代码