当前位置: 首页 > >

素数筛选的写法

发布时间:

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


单线程:



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 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 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 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 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 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数组。



友情链接: