算法：数学问题

• 204 计数质数
  快速计算小于n的质数个数的厄拉多塞筛法：
  先将 2－N 的各数放入表中，然后在 2 的上面画一个圆圈，然后划去 2 的其他倍数；第一个既未画圈又没有被划去的数是 3，将它画圈，再划去 3 的其他倍数；现在既未画圈又没有被划去的第一个数是 5，将它画圈，并划去5的其他倍数……依次类推，一直到所有小于或等于N的各数都画了圈或划去为止。

    public int countPrimes(int n){
        int i = 2;
        int num[] = new int[n];
        while (i < n){
            if (num[i] == 0) {
                num[i] = 1;
                for (int j = i + i; j < n; j += i) {
                    num[j] = -1;
                }
            }
            i++;
        }
        int count = 0;
        for (int j = 2; j<n; j++){
            if (num[j] == 1){
                count++;
            }
        }
        return count;
    }

• 326 3的幂
  进制转换：将n转换为三进制数，然后判断其是否符合“100...0”的格式

    public boolean isPowerOfThree(int n) {
        return Integer.toString(n, 3).matches("^10*$");
    }

整数限制：int范围内，最大的3的幂是，因此所有的3的幂都是这个数的除数。

  public class Solution {
      public boolean isPowerOfThree(int n) {
          return n > 0 && 1162261467 % n == 0;
      }
  }

• 50 Pow(x, n)
  快速幂算法：
  

private double fastPow(double x, long n) {
        if (n == 0) {
            return 1.0;
        }
        double half = fastPow(x, n / 2);
        if (n % 2 == 0) {
            return half * half;
        } else {
            return half * half * x;
        }
    }
    public double myPow(double x, int n) {
        long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }

        return fastPow(x, N);
    }

• 69 x 的平方根
  牛顿迭代法：使用函数的切线来近似计算函数零值
  本题中求，可令，从点开始迭代，
  的切线函数为，
  取，得，令
  迭代，直到x_0变化很小。

    def mySqrt(self, x):
        if x < 0:
            raise Exception('不能输入负数')
        if x == 0:
            return 0
        # 起始的时候在 1 ，这可以比较随意设置
        cur = 1
        while True:
            pre = cur
            cur = (cur + x / cur) / 2
            if abs(cur - pre) < 1e-6:
                return int(cur)

• 166 分数到小数
  长除法：每次比对当前余数是否出现过，若出现，则得到循环节；否则，添加商，重置被除数。

        ...
        while (!rems.contains(num)){
            rems.add(num);
            num *= 10;
            quo = num / sor;
            num = num % sor;
            res += quo;
            if (num == 0) {
                if (numerator>0^denominator>0)
                    return "-" + res;
                else
                    return res;
            }
        }
        ...