求超越，计算小于等于N的素数个数

        最近两天和群里的朋友讨论计算小于等于N的素数的个数。最直接的算法就是对于每一个数i，计算i除以从2到i的平方根，任意一个能除尽都说明i不是素数。但这种算法效率很低，还有很大的改进空间，也有不同方式改进。

        liuyh17211的思路是改进算法，根据算术基本定理，任何合数都可以表示为两个或多个素数的乘积，所以判断i是否是素数的只需要计算i除以从2到i的平方根之间的素数即可，另外java计算平方根的算法效率也不高，用这种思路改造之后的算法效率大幅提高，N为10000000时花费时间大约为朴素算法的1/7左右，而且这种方法对单核或多核的机器都有效。但这种算法只使用了一个线程，在多核处理器上没有充分利用资源。

        群友淘宝定山提供的思路是利用多线程，充分利用机器cpu，不过没有在算法上做太多优化，这种方式和宿主机的cpu核心数与使用的线程数密切相关，效果也非常明显，在他的四核机器上，使用8个线程的情况下，计算时间几乎是朴素方法的1/4多一点儿。总体来说多线程比起算法优化效果稍差一点儿。

        liuyh17211想如果把这两种优化方式结合起来效果应该会更好，首先单线程计算到N的平方根的素数数组，然后再用多线程分段计算素数个数，最后汇总。不过这种方式算法比较复杂，代码也很长。算法完成后，在我的双核四线程机器上用4个线程跑一下，所用时间大约是优化算法的40%。

        周末 liuyh17211把代码拿到家里的单核机器上测了一下，发现了另外一个情况，在单核的机器上，多线程的作用比较小，而优化算法的收益几乎没有损失。

        目前这个算法在多核机器上效率很高，在此征求效率更高的算法和改进思路，也欢迎到Java Developers 67844123交流。

 

附上所有代码，再次感谢淘宝定山提供的多线程计算代码：

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.FutureTask;

/**
 * 计算素数个数方法对比
 * @author [e-mail]
 */
public class PrimeCount {
	
	//线程数
	private static final int cpuNum = Runtime.getRuntime().availableProcessors();
	
	/**
	 * @param args
	 * @throws Exception 
	 */
	public static void main(String[] args) throws Exception {
		int max = 10000000;
		long begin = System.currentTimeMillis();
		int count = primaevalCounting(max);
		long end = System.currentTimeMillis();
		System.out.println("primaevalCounting prime count=" + count + ",time cost=" + (end - begin)+"ms");
		begin = System.currentTimeMillis();
		count = optimizedCounting(max);
		end = System.currentTimeMillis();
		System.out.println("optimizedCounting prime count=" + count + ",time cost=" + (end - begin)+"ms");
		begin = System.currentTimeMillis();
		count = multThreadPrimaevalCounting(max);
		end = System.currentTimeMillis();
		System.out.println("multThreadPrimaevalCounting prime count=" + count + ",time cost=" + (end - begin)+"ms");
		begin = System.currentTimeMillis();
		count = multThreadOptimizedcounting(max);
		end = System.currentTimeMillis();
		System.out.println("multThreadOptimizedcounting prime count=" + count + ",time cost=" + (end - begin)+"ms");
		
		System.exit(0);
	}
	
	/**
	 * 单线程 + 原始算法
	 * 最差的算法
	 * @param x
	 * @return
	 */
	public static int primaevalCounting(int x){
		
		int count = 0;
		
		for(int i = 2 ; i <= x ; i++){
			
			boolean isPrime = true;
			int sqrt = (int)Math.sqrt(i);
			
			for(int j = 2 ; j <= sqrt ; j++){
				if(i % j == 0){
					isPrime = false;
					break;
				}
			}
			
			if(isPrime){
				count++;
			}
		}
		
		return count;
	}
	
	/**
	 * 单线程 + 优化算法
	 * 在单核cpu上效率很高
	 * @param N
	 * @return
	 */
	private static int optimizedCounting(int N){
		
		int n = (int)Math.sqrt(N);
		int[] primeList = new int[n];
		int max = 0;
		  
		int primeCount = 0,d = 1,product = 1;
		boolean isPrime = true;
		
		for(int i = 2 ; i < N ; i++){
			
			if(i > product){
				d++;
				product = d*d;
			}  
		   
			for(int j = 0 ;  j < max ; j++){
				int primeNum = primeList[j];
				
				if(primeNum > d){ 
					break;
				}
				
				if(i%primeNum == 0){
					isPrime = false;
					break;
				}
			}
		   
			if(isPrime){
			    if(i < n){
			    	primeList[primeCount] = i;
			    	max++;
			    }
			    primeCount++;
			}
			
			isPrime = true;
		}
		  
		return primeCount;
	}
	
	/**
	 * 多线程 + 原始算法
	 * @param x
	 * @return
	 */
	public static int multThreadPrimaevalCounting(int x) throws Exception{
		
		int threadNum = cpuNum > 4 ? cpuNum : 4;
		int size = x/threadNum;
		int count = 0;
		
		List<PrimaevalCounting> countList = new ArrayList<PrimaevalCounting>();
		List<FutureTask<Integer>> taskList = new ArrayList<FutureTask<Integer>>();
		
		ExecutorService exec = Executors.newFixedThreadPool(5);
		PrimaevalCounting first = new PrimaevalCounting(2, size);
		countList.add(first);
		FutureTask<Integer> task = new FutureTask<Integer>(first);
		exec.submit(task);
		taskList.add(task);
		
		for(int i=1;i<threadNum;i++){
			
			PrimaevalCounting pre = countList.get(i-1);
			int begin = pre.end+1;
			int end = begin +size;
			
			if(end>x){
				end=x;
			}
			
			PrimaevalCounting counter = new PrimaevalCounting(begin, end);
			countList.add(counter);
			task = new FutureTask<Integer>(counter);
			
			exec.submit(task);
			taskList.add(task);
		}
		
		for(FutureTask<Integer> t : taskList){
			count += t.get();
		}
		
		return count;
	}
	
	/**
	 * 原始算法的多线程辅助类
	 * @author [e-mail]
	 *
	 */
	public static class PrimaevalCounting implements Callable<Integer> {

		public int begin = 0;
		public int end = 0;

		public PrimaevalCounting(int begin, int end) {
			this.begin = begin;
			this.end = end;
		}

		@Override
		public Integer call() throws Exception {
			int c = 0;
			for (int i = begin; i <= end; i++) {
				int s = (int) Math.sqrt(i);
				boolean f = true;
				for (int j = 2; j <= s; j++) {
					if (i % j == 0) {
						f = false;
						break;
					}
				}
				if (f) {
					c++;
				}
			}
			return c;
		}
	}
	
	/**
	 * 多线程 + 优化算法计算
	 * @param x
	 * @return
	 * @throws Exception
	 */
	public static int multThreadOptimizedcounting(int x) throws Exception {
	
		int threadNum = cpuNum > 4 ? cpuNum : 4;
		int size = x / threadNum;
		int count = 0;
		
		List<OptimizedCounting> countList = new ArrayList<OptimizedCounting>();
		List<FutureTask<Integer>> taskList = new ArrayList<FutureTask<Integer>>();		
		int[] primeArray = initPrimeArray(x);
		
		ExecutorService exec = Executors.newFixedThreadPool(10);
		OptimizedCounting first = new OptimizedCounting((int)Math.sqrt(x) + 1, size, primeArray);
		countList.add(first);	
		
		FutureTask<Integer> task = new FutureTask<Integer>(first);
		exec.submit(task);		
		taskList.add(task);
		
		for(int i = 1 ; i < threadNum ; i++){
			
			OptimizedCounting pre = countList.get(i-1);
			int begin = pre.end+1;
			int end = begin +size;
			
			if(end > x){
				end=x;
			}
			
			OptimizedCounting counter = new OptimizedCounting(begin, end, primeArray);
			countList.add(counter);
			task = new FutureTask<Integer>(counter);
			
			exec.submit(task);
			taskList.add(task);
		}
		
		for(FutureTask<Integer> t : taskList){
			count += t.get();
		}
		
		return count + primeArray.length;
	}
	
	/**
	 * 初始化从2到x的平方根之间的素数，用于检查数是否是素数
	 * @param x
	 * @return
	 */
	private static int[] initPrimeArray(int x) {
		
		int n = (int)Math.sqrt(x);
		int[] primeArray = new int[n];
		int max = 0;
		
		int primeCount = 0,d = 1,product = 1;
		boolean isPrime = true;
		
		for(int i = 2 ; i <= n ; i++){
			
			if(i > product){
				d++;
				product = d * d;
			}		
			
			for(int j = 0 ;  j < max ; j++){
				int primeNum = primeArray[j];
				if(primeNum > d){ 
					break;
				}
				if(i % primeNum == 0){
					isPrime = false;
					break;
				}
			}
			
			if(isPrime){
				if(i < n){
					primeArray[primeCount] = i;
					max++;
				}
				primeCount++;
			}
			isPrime = true;
		}
		
		return Arrays.copyOf(primeArray, max);
	}

	/**
	 * 优化算法的多线程计算辅助类
	 * @author [e-mail]
	 *
	 */
	public static class OptimizedCounting implements Callable<Integer> {
	
		private int begin = 0;
		private int end = 0;
		private int[] primeArray;
		
		public OptimizedCounting(int begin, int end, int[] primeArray) {
			this.begin = begin;
			this.end = end;
			this.primeArray = primeArray;
		}
		
		@Override
		public Integer call() throws Exception {
			
			int c = 0;
			//为了避免每次都求开平方，引入两个辅助数据
			int d = (int)Math.sqrt(begin) + 1,prod = begin;
			boolean isPrime = true;
			
			for (int i = begin ; i <= end ; i++) {
				if(i > prod){
					d++;
					prod = d * d;
				}
				
				for (int j = 0 ; j < primeArray.length && primeArray[j] <= d ; j++) {
					if (i % primeArray[j] == 0) {
						isPrime = false;
						break;
					}
				}
				if (isPrime) {
					c++;
				}
				isPrime = true;
			}
			return c;
		}	
	}
}