所谓素性测试是检测一个数是否为素数的测试。而对素数的研究是有很长一段历史，把素数的东西写成一本书的话也许得上千页，而现代密码学又加深了科研工作者对素数的研究，今天就以输出100以内的素数的为例，讲讲素性测试的几种方法。
1.试除法
这可能是每个学过计算机的朋友都敲过的代码，原理就是从判断2到sqrt(n)或者n/2能不能整除n，若能整除就不是素数。
public class SuXingCeShi {
public static void main(String[] args) {
int n = 100;
SuXingCeShi robot = new SuXingCeShi();
robot.shichu(n);
}
private void shichu(int n) {
for(int i = 2; i <= n; i++){
int j;
for(j = 2; j < Math.sqrt(i); j++){
if(i % j == 0)
break;
}
if(j > Math.sqrt(i))
System.out.print(i + " ");
}
System.out.println();
}
}
2.eratosthenes筛选法（埃拉托斯特尼筛法）
步骤：
1.列出2,3,4..........100
2.选取第一个没被处理过的数（第一次为2）
3.去掉以2为因数的所有数
4.如果下一个素数小于sqrt(100)跳转到第二步
5.结束
以下是来至wikipedia介绍该算法的图片，挺直观的，可以看看
public class SuXingCeShi {
public static void main(String[] args) {
int n = 100;
SuXingCeShi robot = new SuXingCeShi();
robot.eratosthenesShaixuan(n);
}
public void eratosthenesShaixuan(int n) {
// TODO Auto-generated method stub
int[] a = new int[n+1];//申请n+1个空间
a[0] = a[1] = -1;//剔除0，1
for(int i = 2; i < n+1; i++)
a[i] = i;
int temp = 2;
double edge = Math.sqrt(n);//边界值
while(temp <= edge){
if(a[temp] == -1){//如果a[temp]是合数
temp++;
continue;
}
//如果a[temp]是质素，去掉以它为因数的合数
for(int i = 2; i <= (a.length-1)/temp ; i++){
a[temp*i] = -1;
}
temp++;
}
for(int i = 0; i < a.length; i++){
if(a[i] != -1)
System.out.print(a[i] + " ");
}
System.out.println();
}
}
3.一种更快的筛选算法
eratosthenes算法在拆选的时候进行了重复拆选，比如数30，2、3、5都对其进行了拆选，有没有一种更好的方法，让每个合数只被拆选一次呢？
这个算法稍稍有些难理解，先看代码
public class SuXingCeShi {
public static void main(String[] args) {
int n = 100;
SuXingCeShi robot = new SuXingCeShi();
robot.caixuan(n);
}
void caixuan(int n){
boolean flag[] = new boolean[n+1];
int prime[] = new int[n+1];
int prime_num = 0;
for(int i=0; i<=n; i++){
flag[i] = true;//把所有数都看成素数
}
for(int i = 2; i <= n; i++){
if(flag[i] == true){
prime[prime_num++] = i;//记录素数
}
for(int j=0; j <prime_num && prime[j]*i <= n; j++){
flag[prime[j]*i] = false;//把合数赋值成false
if(i % prime[j] == 0)//理解就是
break;
}
}
for(int i = 0; i < prime.length; i++){
if(prime[i] != 0)
System.out.print(prime[i] + " ");
}
}
}
我们先申请一个 boolean[] flag 来进行拆选，再申请一个 int[] prime 记录素数，在第二个for循环中进行判断， if(flag[i] == true) 把它记录下来（因为我们把i之前的数都拆选过了，看二重for循环）比如现在 i = 9 ; i 前面的素数有 2，3，5，7 都记录在 prime[] 里了 然后遍历 prime 数组， j = 0 时， flag[prime[j]*i] = false 意思是把 flag[2*9] 赋值成 false , j = 1 时候我们把 flag[3*9] 赋值成 false ，关键是下面这句话， if(i % prime[j] == 0) break ;它是整个算法的核心，为什么把 flag[27] 筛出去之后就不再筛 flag[36] 和 flag[45] 了呢？因为当 i = 18 的时候 flag[2*18] 把 flag[36] 给筛出去了，但是没有筛选 flag[3*18],flag[4*18] ,因为在 flag[2*27] 和 flag[2*36] 分别拆选过了。再举个例子比如 i = 35 ,当 flag[2*35] 拆选过后 ,还得筛选 flag[3*35](假设n>105) ，因为 flag[105] 没法再由其他形式拆选了，所以用这样方式才保证了每个合数被筛选且仅被筛选一次。