介绍

质数：在大于1的整数中，如果只包含1和本身这两个约数，就被称为质数（素数）

解法

枚举从2 ~ N的每一个数
实际上不用枚举到N，只需要枚举到√N就行

注意：

1. 不要使用sqrt()函数，直接求√n，因为该函数运算较慢

2. 注意数据溢出，i * i <= n可能会溢出，推荐使用i <= n / i

   public static boolean isPrime(int n) {
   // 枚举到√n,注意溢出
   for(int i = 2; i <= n / i; i++)
   // 如果i可以整除n,说明n不是素数，直接return false
   if(n % i == 0)
   return false;
   // 说明n是素数
   return true;
   }

   public static boolean isPrime(int n){
   int [] arr = new int[n+1];
   // 1:质数 0:非质数
   Arrays.fill(arr,1);

   for(int i = 2; i <= n; i++){
       if(arr[i] == 1){
           // 将i的倍数去除掉
           for(int j = i+i; j <= n; j += i){
               arr[j] = 0;
           }
       }
   }
   return arr[n] == 1 ? true : false;

   }

   public static boolean isPrime3(int n){
   // 质数集合
   List primes = new ArrayList<>();
   int [] arr = new int[n+1];
   // 1:质数 0:非质数
   Arrays.fill(arr,1);

   for(int i = 2; i <= n; i++){
       if(arr[i] == 1)
           primes.add(i); // 添加集合中
       // 筛选，
       for(int j = 0; j < primes.size() && primes.get(j) <= n / i; j++){
           // 标记
           arr[i*primes.get(j)] = 0;
           // 保证每个合数只会被它的最小质因数筛去，减少冗余
           if(i % primes.get(j) == 0)
               break;
       }
   }
   return arr[n] == 1 ? true : false;

   }

集合可以换成数组，用一个变量来保存当前集合中的质数数量，相当于下标

全部代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Prime{

    public static void main(String[] args) {
        System.out.println(isPrime(430348));
        System.out.println(isPrime2(430348));
        System.out.println(isPrime3(430348));
    }

    // 暴力枚举
    public static boolean isPrime(int n) {
        // 防止溢出
        for(int i = 2; i <= n / i; i++)
            if(n % i == 0)
                return false;
        return true;
    }

    // 埃氏筛法
    public static boolean isPrime2(int n){
        int [] arr = new int[n+1];
        // 1:质数   0:非质数
        Arrays.fill(arr,1);

        for(int i = 2; i <= n; i++){
            if(arr[i] == 1){
                // 将i的倍数去除掉
                for(int j = i+i; j <= n; j += i){
                    arr[j] = 0;
                }
            }
        }
        return arr[n] == 1 ? true : false;
    }

    // 线性筛法
    public static boolean isPrime3(int n){
        // 质数集合
        List<Integer> primes = new ArrayList<>();
        int [] arr = new int[n+1];
        // 1:质数   0:非质数
        Arrays.fill(arr,1);

        for(int i = 2; i <= n; i++){
            if(arr[i] == 1)
                primes.add(i); // 添加集合中
            // 筛选，
            for(int j = 0; j < primes.size() && primes.get(j) <= n / i; j++){
                // 标记
                arr[i*primes.get(j)] = 0;
                // 保证每个合数只会被它的最小质因数筛去，减少冗余
                if(i % primes.get(j) == 0)
                    break;
            }
        }
        return arr[n] == 1 ? true : false;
    }
}

运行截图