第二夜——质数

大家好，我是平头哥，今天给大家分享的内容为如何求质数。

什么是质数

百度百科上说质数（prime number）又称素数，有无限个。(话说prime number不应该翻译成主要数嘛)。

质数的定义

质数又称素数。一个大于1的自然数，除了1和它自身外，不能整除其他自然数的数叫做质数；否则称为合数。

筛选法求质数

1. 用一个布尔数组isPrime表示某个范围range内的整数是否为质数，如果下标为k的数组元素的值为true，则表示
   整数k是质数；否则，不是质数。因此，初始时，isPrime[1]位false，isPrime[2]为true，数组中其他元素的值均为true.
2. 遍历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);

    }
}