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

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的最简真分数个数。

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

感觉有点动态规划的意思。首先要懂得什么情况不是最简。
以30为例子：30=235，意味着分母为2/3/5的倍数的时候就不是最简，要做的是把这部分删掉。
有兴趣的话，可以去看看：线性筛和埃氏筛

public  long properFractions(long n) {
        if (n==1) return 0;
        //r:相当于返回值，剩余最简个数
        long r=n;
        for(long d=2;d*d<=n;d++){
            //其实进入这个if的一定是质数，合数在前面已经去掉了，可以拿210看一下
            if(n%d == 0){
                //这里可以缩小规模，原因是可约分数必然为某因子的倍数，这部分在本次筛选已经去除了，后面不必重复
                //举例子：12的因子2*2*3，对于4的倍数，在删掉2的倍数的时候已经删过一遍了，不用重复删，所以这里缩小规模用while
                while(n%d == 0){
                    n/=d;
                }
                //假设是12，我们知道：待选，1 2 3 4 5 6 7 8 9 10 11 12，对于d=2的情况，2 4 6 8 10 12 都满足，共删除12/2，共6个
                r-=r/d;
            }
        }
        //对于最大因子只有一个的情况，比如12=2*2*3,3只有一个，最后一个因子的倍数，没有筛掉，所以这种情况就需要再筛一次；
        //8=2*2*2，这种情况，直接把n约到1了，就不用再筛一次
        if(n>1) r-=r/n;
        return r;
    }