一、素数及相关概念
素数又称质数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做素数；否则称为合数（规定1既不是质数也不是合数）。
1、素数的性质
- 质数只有两个因数：1和本身。
- 任何大于1的自然数，要么本身是质数，要么可以分解为几个质数之积，且这种分解是唯一的。
- 质数的个数是无限多的。
- 若n为正整数，在n²到(n+1)²之间至少有一个质数
- 若n为大于等于2的正整数，则n到n!之间至少有一个质数
- 若质数p为不超过n(n≥4)的最大质数，则p＞n/2
- 所有大于10的质数中，个位数只有1，3，7，9
- 在一个大于1的数a和它的2倍之间（即区间（a, 2a]中）必存在至少一个素数。
- 存在任意长度的素数等差数列。
2、有关素数的猜想
- 哥德巴赫猜想：是否每个大于2的偶数都可写成两个素数之和？
- 孪生素数猜想：孪生素数就是差为2的素数对，例如11和13。是否存在无穷多的孪生素数？
- 斐波那契数列内是否存在无穷多的素数？
- 是否有无穷多个的梅森素数？（所谓梅森数，是指形如2ᵖ－1的一类数，其中指数p是素数，常记为Mp。如果梅森数是素数，就称为梅森素数。）
- 是否存在无穷个形式如X2+1素数？
3到881之内的孪生素数
2至54的素数
二、素数的判断方法
1、根据性质去判断
我们都知道素数的性质是除了1和它自身外，不能被其他自然数整除，所以第一个方法就是从2到n-1一个个去判断是否有数可以除以该数且为0,即 n%i==0；如果有则不是素数，如果遍历一遍都没有数可以整除它，则就是素数。
public class Main { public static boolean isPrime(int n){ if (n <= 3) { return n > 1; } for (int i=2;i<n;i++){ if (n%i==0) return false; } return true; } public static void main(String[] args) { for (int i=2;i<100;i++){//找2到100之间的素数 if (isPrime(i)) System.out.print(i+" "); //2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 } } }
2、改进1方法（缩小比较范围√n）
看了方法一，大家觉得浪费了很多时间，不必一直循环到n-1，因为如果a*b=n，则其中必有一个大于sqrt(n) ，一个小于sqrt(n),，所以我们把循环范围缩小到√n。
public class Main { public static boolean isPrime(int n){ if (n <= 3) { return n > 1; } for (int i=2;i<=Math.sqrt(n);i++){ if (n%i==0) return false; } return true; } public static void main(String[] args) { for (int i=2;i<100;i++){//找2到100之间的素数 if (isPrime(i)) System.out.print(i+" "); //2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 } } }
3、再次分析素数的特点，得出规律
其实素数还有一个特点，就是它总是等于 6x-1 或者 6x+1，其中 x 是大于等于1的自然数。
这个结论其实很容易论证。首先 6x 肯定不是质数，因为它能被 6 整除；然后6x+2 肯定也不是质数，因为它还能被2整除；依次类推，6x+3 肯定能被 3 整除；6x+4 肯定能被 2 整除。那么，就只有 6x+1 和 6x+5 (相当于6x-1) 可能是质数了。所以循环的步长可以设为 6，然后每次只判断 6 两侧的数即可。我们也可以通过孪生素数可以很清楚的验证这个规律。
这样我们又可以更加便捷的找出想要找的素数。
public class Main { public static boolean isPrime(int num) { if (num <= 3) { return num > 1; } // 不是在6的倍数两侧的一定不是素数数 if (num % 6 != 1 && num % 6 != 5) { return false; } //同样的在6的倍数两侧的数也不一定是素数，还是要判断 int sqrt = (int) Math.sqrt(num); for (int i = 5; i <= sqrt; i += 6) { if (num % i == 0 || num % (i + 2) == 0) { return false; } } return true; } public static void main(String[] args) { for (int i=2;i<100;i++){//找2到100之间的素数 if (isPrime(i)) System.out.print(i+" "); //2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 } } }
问题：枚举n以内所有素数
上面方法都是用来判断是不是,但是当叫你求n内素数的个数时，这样一个个去判断的时间复杂度过大，太费时间，这就需要下面的方法了。
4、埃氏筛法（埃拉托斯特尼筛法）
埃氏筛法就是先把所有整数列出来，然后把2的倍数全部剔除，然后是三的，以此类推，遍历所有素数，把倍数全部划去。对于某个数字i，如果没被划去，他一定是素数，因为他不是任何2到i-1数字的倍数。然后就开始划它的倍数就好。
import java.util.Arrays; public class Main { static int isPrime(int n) { int[] b=new int[n+1];//通过数组b的值，为1就是素数 int p=0;//记录素数个数 for(int i=0;i<n+1;i++) b[i]=1; b[0]=0; b[1]=0; //准备完毕 for(int i=2;i<=n;i++){ if(b[i]!=0){ p++;//i是素数即i++;然后剔除i的倍数 for(int j=2*i;j<=n;j+=i) b[j]=0;//剔除倍数 } } return p;//返回素数个数 } public static void main(String[] args) { //找2到100之间的素数 System.out.print(isPrime(100));//25 //2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 } }
或者使用boolean值来进行辨别是否为素数，我们可以埃氏筛法把所有素数找出来，然后继续O（1）操作来判断i是否为素数
public class Main { public static void main(String[] args) { boolean[] isPrime=new boolean[100+1]; //true为素数 isPrime[0]=false; isPrime[1]=false; for (int i=2;i<100+1;i++) isPrime[i]=true; for (int i=2;i<100+1;i++){ if (isPrime[i]){ for (int j=2;i*j<100+1;j++) isPrime[i*j]=false; } } } }
很上面一样可以进行优化不必一直循环到n，到Math.sqrt(n)就可以。
public class Main { public static void main(String[] args) { boolean[] isPrime=new boolean[100+1]; //true为素数 isPrime[0]=false; isPrime[1]=false; for (int i=2;i<100+1;i++) isPrime[i]=true; for (int i=2;i<Math.sqrt(101);i++){ if (isPrime[i]){ for (int j=2;i*j<100+1;j++) isPrime[i*j]=false; } } for (int i=2;i<isPrime.length;i++){ if (isPrime[i]) System.out.print(i+" "); //2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 } } }
5、欧拉筛法（埃氏筛法的优化版）
在埃氏筛法中，由于一个数可以既是一个素数的倍数，又是另一个素数的倍数，可以发现这会出现重复标记的情况，即同一个数被筛掉了不止一次，如果n值过大，则也是一笔不小的时间开销。
欧拉筛法就是在埃氏算法的基础上多了判断的步骤，从而消去了这种重复标记的情况，核心思路是用合数中的一个因数筛掉这个合数。
public static void eulerSieve(int n){ boolean[] isPrime = new boolean[n+1]; int[] Prime=new int[n];//存放素数的数组，false为素数 isPrime[0] = isPrime[1] = true;//数字0和1都不是素数，所以赋true int count = 0; Prime[count++] = 2;//把2放进素数表 for (int i = 2; i <n+1; i++) { if (!isPrime[i])//若当前数是素数 Prime[count++] = i;//则存入素数数组 for (int j = 0; j < count && Prime[j] * i < n+1; j++) { isPrime[i * Prime[j]] = true; if (i % Prime[j] == 0) break;//避免重筛,使得程序更有效率 } } }
可以看 欧拉筛法寻找10以内的素数，可以发现完全没有重复判断的数，因为多了一个判断，大幅增加了筛素数的速度，时间复杂度为O（n）。
