求超越，计算小于等于N的素数个数
程序员文章站
2022-03-13 09:52:05
...
最近两天和群里的朋友讨论计算小于等于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;
}
}
}
下一篇： 求1~n之间的素数
推荐阅读
-
问题描述 输入一个自然数n，求小于等于n的素数之和
-
输入一个自然数n，求小于等于n的素数之和？
-
JS实现计算小于非负数n的素数的数量算法示例
-
求哪几个数字之和接近某一个给定的值（小于等于）
-
输入正整数n（n大于等于2）,求不大于n的全部质数（素数）【其中一种优化算法】
-
妙妙屋-求小于n的所有正整数中1的个数
-
求哪几个数字之和接近某一个给定的值（小于等于）
-
1002 写出这个数 (20)（20 分） 读入一个自然数n，计算其各位数字之和，用汉语拼音写出和的每一位数字。 输入格式：每个测试输入包含1个测试用例，即给出自然数n的值。这里保证n小于10^10
-
小于等于n的素数之和
-
JS实现计算小于非负数n的素数的数量算法示例