第二夜——质数

2018-12-26  本文已影响0人  MXi4oyu

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

什么是质数

百度百科上说质数(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);

    }
}

上一篇下一篇

猜你喜欢

热点阅读