大家好，我是平头哥，今天给大家分享的内容为如何求质数。
什么是质数
百度百科上说质数（prime number）又称素数，有无限个。(话说prime number不应该翻译成主要数嘛)。
质数的定义
质数又称素数。一个大于1的自然数，除了1和它自身外，不能整除其他自然数的数叫做质数；否则称为合数。
筛选法求质数
- 用一个布尔数组isPrime表示某个范围range内的整数是否为质数，如果下标为k的数组元素的值为true，则表示
整数k是质数；否则，不是质数。因此，初始时，isPrime[1]位false，isPrime[2]为true，数组中其他元素的值均为true. - 遍历isPrime数组，下标从1开始，到range的开方结束。根据“质数的倍数不是质数”的规则，改变isPrime数组的值。
遍历结束后，isPrime数组中下标为非质数的整数的元素值为false，而下标为质数的整数的元素值还是true。
画一下重点啊，质数的倍数不是质数
源码如下
import java.util.Arrays;
public class PrimerNumber {
/**
* 用筛选法求质数
* @param range
* @return
*/
private boolean[] sieve(int range){
if(range <=0){
System.out.println("求质数的范围range必须大于0！");
return null;
}
// 用一个布尔数组标识是否为质数，如果下标为质数
// 那么该下标对应的数组元素的值为true
// 比如2是质数，则isPrime[2] =true
// 因为数组下标是从0开始的，所以这里新建的数组大小为range+1
boolean[] isPrime = new boolean[range+1];
isPrime[1] = false; //1不是质数
//用Arrays的fill方法将数组下标从2到range+1之间的元素的值都赋为true
Arrays.fill(isPrime,2,range+1,true);
int n = (int)Math.sqrt(range);
for(int i=1;i<=n;i++){
//如果i是质数，那么i的倍数不是质数
if(isPrime[i]){
for(int j=2*i;j<=range;j+=i){
isPrime[j] = false;
}
}
}
return isPrime;
}
/**
* 显示range范围内的质数
* @param range 范围的上限
*/
public void showPrimerNumber(int range){
boolean[] primes = this.sieve(range);
int number = 0 ;
if(primes!=null){
int size = primes.length;
System.out.println("范围在"+range+"内的质数有:");
for(int i=1;i<size;i++){
if(primes[i]){
System.out.print(i+" ");
//每输出10个质数换行
// number先加1，再跟10做摸运算,如果余数为0，则换行
if(++number % 10 ==0){
System.out.println();
}
}
}
System.out.println();
}
}
public static void main(String[] args){
int range = 200;
PrimerNumber test = new PrimerNumber();
test.showPrimerNumber(range);
}
}
