在Java中判断一个数是不是质数的几种方法

法一最基础的方法代码public static boolean isPrimeBasic(int n) {if (n 2) return false;for (int i 2; i n; i) {if (n % i 0) return false;}return true;}理解在这个代码中是逐个检查的也就是逐个遍历最容易去记法二优化到 √nO(√n)代码public static boolean isPrimeSqrt(int n) {if (n 2) return false;for (int i 2; i * i n; i) {if (n % i 0) return false;}return true;}理解只检查到根号n因为如果n有一个大于根号n的因数那么必然存在一个小于根号n的因数所以这种方法进行了一些优化法三6k±1 优化最经典的高效版本代码public static boolean isPrime6k(int n) {if (n 2) return false;if (n 2 || n 3) return true;if (n % 2 0 || n % 3 0) return false;for (int i 5; i * i n; i 6) {if (n % i 0 || n % (i 2) 0) return false;}return true;}理解在这个方法中在n大于3时6k,6k2,6k3都能被整除而6k1和6k5可表示为6k-1都不能被整除。所以在这里进行了优化法四埃拉托斯特尼筛法筛选1到n的代码public class SieveOfEratosthenes {/*** 埃拉托斯特尼筛法* param n 筛选范围 [0, n]* return 布尔数组isPrime[i] 为 true 表示 i 是素数*/public static boolean[] sieve(int n) {// 1. 创建布尔数组默认所有数都是素数boolean[] isPrime new boolean[n 1];for (int i 0; i n; i) {isPrime[i] true;}// 2. 0 和 1 不是素数isPrime[0] false;isPrime[1] false;// 3. 从 2 开始遍历到 sqrt(n)for (int i 2; i * i n; i) {// 如果 i 是素数则将其倍数标记为合数if (isPrime[i]) {// 从 i*i 开始标记因为更小的倍数已经被更小的素数标记过了for (int j i * i; j n; j i) {isPrime[j] false;}}}return isPrime;}/*** 打印素数列表* param isPrime 筛法结果数组*/public static void printPrimes(boolean[] isPrime) {System.out.println(素数列表);for (int i 0; i isPrime.length; i) {if (isPrime[i]) {System.out.print(i );}}System.out.println();}public static void main(String[] args) {int n 100; // 设置范围boolean[] isPrime sieve(n);printPrimes(isPrime);// 可选统计素数个数int count 0;for (boolean b : isPrime) {if (b) count;}System.out.println(素数个数 count);}}理解一个素数的倍数不是素数因为除了他本身和一外还有别的因数。这个方法主要通过布尔型的函数首先把所有数都标记为真也就都是素数然后再把i的倍数都标记为假最后能筛出所有的素数。法五欧拉筛代码public class EulerSieve {/*** 欧拉筛线性筛求 [0, n] 内的所有素数* param n 范围上限* return 布尔数组isPrime[i] 为 true 表示 i 是素数*/public static boolean[] eulerSieve(int n) {// 结果数组记录每个数是否是素数boolean[] isPrime new boolean[n 1];// 初始化假设所有数都是素数for (int i 0; i n; i) {isPrime[i] true;}isPrime[0] false;isPrime[1] false;// 用于存储已经找到的素数int[] primes new int[n 1];int count 0; // 当前已找到的素数个数// 从 2 开始遍历到 nfor (int i 2; i n; i) {if (isPrime[i]) {// i 是素数加入素数表primes[count] i;}// 用当前数 i 乘以每个已找到的素数标记合数for (int j 0; j count i * primes[j] n; j) {// 标记 i * primes[j] 为合数isPrime[i * primes[j]] false;// 关键如果 i 能被 primes[j] 整除就停止循环if (i % primes[j] 0) {break;}}}return isPrime;}public static void main(String[] args) {int n 100;boolean[] isPrime eulerSieve(n);System.out.println(素数列表);for (int i 0; i n; i) {if (isPrime[i]) {System.out.print(i );}}}}理解我是不是可以这么理解欧拉筛对于一个数只会把最小质因数的倍数筛掉。