求超越，计算小于等于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 [email protected] */ 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 [email protected] * */ 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 [email protected] * */ 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; } } }