一、简介

什么是质数？

质数也称素数，是指除 1 和它本身以外没有其他因数的正整数。比如，2、3、5、7、11、13 等都是质数，因为它们除 1 和它本身以外没有其他因数。相反，像 4、6、8、9、10 等就不是质数，因为它们都可以被 2 或其他数整除。质数在数学中十分重要，也有很多实际应用。

常用方法：

求质数常用的方法有以下几种：

试除法：从2开始，依次用2，3，4，……，n-1（n为待判断的数）去除n，如果都不能整除，则n为质数。但这种方法比较耗时，不太适用于大数的判断。

埃氏筛法：先把2到N的各个数放入表中，然后在2的上面画一个圆圈，然后删除表中其他数字中2的倍数；第一个既未画圈又没有被划掉的数字是3，将它画圈，再划掉表中其他数字中它的倍数；以后依次类推，即在未画圈的数中，选择最小的素数，然后画圈，再划掉表中它的倍数，依次进行，直到把不大于N的n所有的素数都筛选出来。

线性筛法：和埃氏筛法相似，但是在线性筛法中，每个合数只会被它的最小质因子筛选掉，而不重复。这个方法在求解大范围质数时效率更高。
…

二、方法

1. 试除法

优点：

算法简单易懂，容易实现。> 2. 在小范围内的判断质数，效率较高。

缺点：

对于大数的判断，效率很低，时间复杂度为O(n)。
如果判断的数是一个较大的质数，需要整除到它的平方根，这会消耗大量时间。
空间复杂度较高，需要存储2到n-1的每个自然数，占用大量的内存空间。

因此，试除法适合用于小范围内的质数判断，但不适用于大范围的质数筛选。

模板：

public class Main {public static void main(String[] args) {//求1~N(不包括N)之前所有的质数int N = 10000;int[] num = new int[N];//保存质数int index = 0;for (int i = 1; i < N; i++) {if (check(i)) {num[index++] = i;}}}private static boolean check(int a) {// TODO Auto-generated method stubif (a == 1 || a == 0) {return false;}for (int i = 2; i < a; i++) {if (a % i == 0) {return false;}}return true;}
}

2. 线性筛法

优点：

在一定范围内，时间复杂度是线性的，效率高，通常要比试除法快得多。

空间复杂度较低，只需要存储1到n的每个自然数和质数表。

实现简单，易于理解和修改。

筛选出的质数是按顺序排列的，方便进行后续的计算。

缺点：

算法难以突破线性复杂度，无法应对更大范围的质数筛选需求。

由于需要存储质数表，空间占用也会随着质数的增多而增加，在极端情况下可能会占用很大的内存空间。

对于某些质数，可能会被重复标记，导致效率的降低。

因此，线性筛法适用于中等规模的质数筛选，不适用于极大规模的情况。

模板：

public class Main {public static void main(String[] args) {//求1~N(不包括N)之前所有的质数int N = 10000;boolean[] bool = new boolean[N];//保存质数int[] num = new int[N];int index = 0;for (int i = 2; index < N ; i++) {if (!bool[i]) {num[index++] = i;}for (int j = 0; num[j] * i < N; j++) {bool[num[j] * i] = true;if (i % num[j] == 0) {break;}}}}
}