Prime number 质数相关

什么是质数？在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数，比如：2,3,5,7,11...

什么是合数？比1大但不是素数的数称为合数。1和0既非素数也非合数。合数是由若干个质数相乘而得到的， 比如：4,6,8,9,10...

如何判定一个数是否位质数？

public class Main {
    public static void main(String[] args) {
        System.out.println(isPrime(3));
    }
    //一个数N的最大质数因子<=sqrt(N),因此我们只需要判定到 i*i <= n 即可
    private static boolean isPrime(int n) {
        for(int i = 2; i * i <= n; i++) {
            if(n % i == 0) return false;
        }
        return true;
    }
}

给出一个数字n，列出小于n的所有质数

    private void countPrime(int num, List<Integer> set) {
        //初始化2～num+1认为都不是质数
        boolean[] isNotPrime = new boolean[num + 1];
        //逐个进行判定是否位质数
        for(int i = 2; i <= num; i++) {
            //如果被标记为不是质数，那么直接continue
            if(isNotPrime[i]) continue;
            //否则就是质数
            set.add(i);
            //如果是质数，那么标记所有它的倍数数字为合数
            for(int j = i + i; j <= num; j = j + i) {
                isNotPrime[j] = true;
            }
        }
    }