204. Count Primes

质数定义: 在大于1的自然数中，除了1和它本身以外不再有其他因数

public int countPrimes(int n) {
    boolean[] notPrime = new boolean[n];
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (notPrime[i]) continue; 
        count++;  // find the first prime in the remaning nums
        for (int j = 2; i * j < n; j++) {
            notPrime[i * j] = true; // delete all the multiples of this prime
        }
    }
    return count;
}

1.返回前10个质数：最直接的试除法[2, n - 1]，在自然数中判断一个数是否为质数，O(n^2):

public static int[] countPrimes(int n) {
    int[] res = new int[n];
    int pointer = 0;
    int num = 2;
    while (pointer < n) {
        if (isPrime(num)) {
            res[pointer] = num;
            pointer++;
        }
        num++;
    }
    return res;
}

public static boolean isPrime(int n) {
    for (int i = 2; i < n; i++) {
        if ((n % i) == 0) return false;
    }
    return true;
}

2.减小试除范围，因为质因数小于等于n/2：

public static boolean isPrime(int n) {
    for (int i = 2; i < (n + 1) / 2; i++) {
        if ((n % i) == 0) return false;
    }
    return true;
}

3.约数成对出现，并且一个在sqrt(n)前面。一个在sqrt(n)后面，所以只用判断到根号n：

public static boolean isPrime(int n) {
    for (int i = 2; i <= Math.sqrt(n) ; i++) {
        if ((n % i) == 0) return false;
    }
    return true;
}

4.Eratosthenes埃拉托斯特尼筛法