素数筛选的写法

分单线程和多线程版本，直接贴代码吧

单线程：

import java.util.BitSet;

/**
 * 单线程版
 * 素数:2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 57 61 67 71 73 79 83 89 97
 */
public class Sieve {
    public static final int MAX = 10000_0000;
    public static void main(String[] args) throws InterruptedException {
        //过滤法是以空间换时间
        BitSet bitSet = new BitSet(); //用位(bit)标记素数，节省空间
        bitSet.set(0, true);
        long t1 = System.currentTimeMillis();
        findSieve(bitSet, MAX);
        long t2 = System.currentTimeMillis();
        int[] sieveArr = getSieveArr(bitSet, MAX);
        System.out.printf("单线程版->%n耗时:%dms %n个数:%d%n", t2 - t1, sieveArr.length);
    }

    /**
     * 转成素数数组
     */
    private static int[] getSieveArr(BitSet bitSet, int max) {
        int[] sieveArr = new int[max - bitSet.cardinality()];
        int n = 0;
        for (int i = 2; i <= max; i++) {
            if(!bitSet.get(i)) sieveArr[n++] = i;
        }
        return sieveArr;
    }

    /**
     * 过滤出素数
     */
    private static void findSieve(BitSet bitSet, int max) {
        int k = 2; //素数
        int sqrt = (int) Math.sqrt(max);
        while(k<=sqrt){
            for (int i = k<<1; i <= max; i+=k) {
                bitSet.set(i, true);
            }
            for (int i = ++k; i <= max; i++) {
                if(!bitSet.get(i)){
                    k = i; break;
                }
            }
        }
    }
}

执行结果：

多线程版：

import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * 多线程版
 * 素数:2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 57 61 67 71 73 79 83 89 97
 */
public class ConcurrentSieve {
    public static final int MAX = 10000_0000;
    public static void main(String[] args) throws InterruptedException {
        final Queue<Integer> baseSieve = baseSieve((int)Math.sqrt(MAX));
        final boolean[] bitSet = new boolean[MAX+1]; 
        bitSet[0] = bitSet[1] = true;
        int threadNum = Runtime.getRuntime().availableProcessors()-3; //cpu线程数
        final CountDownLatch latch = new CountDownLatch(threadNum);//控制住线程等待子线程
        ExecutorService exec = Executors.newFixedThreadPool(threadNum);//创建线程池
        long t3 = System.currentTimeMillis();
        for (int i = 0; i < threadNum; i++) {
            exec.execute(new Runnable() {//创建子线程任务
                @Override
                public void run() {
                    findSieve(bitSet, baseSieve, MAX);
                    latch.countDown();
                }
            });
        }
        latch.await();
        long t4 = System.currentTimeMillis();
        Integer[] sieveArr = getSieveArr(bitSet, MAX);
        System.out.printf("多线程版->%n耗时:%dms %n个数:%d%n", t4 - t3, sieveArr.length);
        exec.shutdown();
    }

    /**
     * 利用boolean数组过滤出素数
     */
    private static void findSieve(boolean[] bitSet, Queue<Integer> baseSieve, int max) {
        Integer m = 2;
        int k = 2;
        while ((m=baseSieve.poll()) != null) {
            k = m; //防止for循环时自动拆箱
            for (int i = k<<1; i <= max; i+=k) {
                bitSet[i] =  true;
            }
        }
    }

    /**
     * 转成素数数组
     */
    private static Integer[] getSieveArr(boolean[] bitSet, int max) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < bitSet.length; i++) {
            if(!bitSet[i]) list.add(i);
        }
        return list.toArray(new Integer[list.size()]);
    }

    /**
     * 生成基础素数队列
     */
    private static Queue<Integer> baseSieve(int base) {
        BitSet bastBitSet = new BitSet();
        int k = 2; //素数
        int sqrt = (int) Math.sqrt(base);
        while(k<=sqrt){
            for (int i = k<<1; i <= base; i+=k) {
                bastBitSet.set(i, true);
            }
            for (int i = ++k; i <= base; i++) {
                if(!bastBitSet.get(i)){
                    k = i; break;
                }
            }
        }
        LinkedBlockingQueue<Integer> baseSieve = new LinkedBlockingQueue<>();
        for (int i = 2; i < bastBitSet.length(); i++) {
            if(!bastBitSet.get(i)){
                baseSieve.offer(i);
            }
        }
        return baseSieve;
    }
}

执行结果：

运行在Windows7系统，8线程cpu。留3个线程资源给系统比较合理
多线程版没有提升太多，相反空间占用率更大些。
BitSet在跑多线程版本时有线程安全问题，直接用位操作虽然能更省空间，但是操作麻烦且代码难以阅读，故直接使用boolean数组。