艾拉托斯特你筛法（java实现）-白红宇

艾拉托斯特你筛法（java实现）

阅读量：4072 次

发布时间：2019-05-25

本文共 1175 字，大约阅读时间需要 3 分钟。

艾拉托斯特你筛法能够非常高效的生成素数序列，原理是剔除所有可能被素数整除的非素数。

给出要筛数值的范围n，找出

n−−√ $\sqrt{n}$ 以内的素数

p1 $p_{1}$ ,

p2 $p_{2}$ ,

… $\dots$ ,

pk $p_{k}$ 。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；不断重复下去……。

以下是java实现代码：

public class PrimeNumber {
       public static void main(String[] args) {        int max = 100;        PrimeNumber pn = new PrimeNumber();        pn.sieveOfEratosthenes(max);    }    boolean[] sieveOfEratosthenes(int max){        boolean[] flags = new boolean[max+1];        int count = 0;//统计一共有多少个素数        int prime = 2;        //初始化，设置flags数组全部为true        for (int i = 0; i < max; i++) {            flags[i] = true;        }        flags[0] = flags[1] = false;        while (prime <= max) {            //剔除prime的倍数            crossOff(flags, prime);            //找出下一个为true的值            prime = getNextPrime(flags, prime);            if (prime >= flags.length) {                break;            }            count++;            System.out.println("prime = "+prime);        }        System.out.println("count = "+count);        return flags;    }    void crossOff(boolean[] flags,int prime){        /*         * 剔除余下的prime倍数的数字，从prime*prime开始，因为如果k*prime且k

以上代码还可以优化计算次数，即只把奇数放进数组，即可减半。

你可能感兴趣的文章