质数/素数

概述

• 质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。
• 2是最小的质数，也是唯一的偶数质数。

判断质数

暴力枚举

• 判断一个数是否为质数，只需要判断到它的平方根即可。

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

埃氏筛法

public static boolean isPrime(int n){
    int [] arr = new int[n+1];
    Arrays.fill(arr,1);
    for(int i = 2; i <= n; i++){
        if(arr[i] == 1){
            for(int j = i+i; j <= n; j += i){
                arr[j] = 0;
            }
        }
    }
    return arr[n] == 1;
}