`
liuyh17211
  • 浏览: 11591 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

求超越,计算小于等于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 liuyh17211@gmail.com
 */
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 liuyh17211@gmail.com
	 *
	 */
	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 liuyh17211@gmail.com
	 *
	 */
	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;
		}	
	}
}

 

分享到:
评论

相关推荐

    《为什么要证明》PPT课件1

    假设有一根比地球赤道长1米的铁丝,如果将地球视为完美的球体,计算铁丝与赤道之间的间隙,我们会发现这个间隙远小于我们直觉上的预期。这个问题旨在强调数学计算的重要性,以及不能仅依赖生活常识做判断。 课程还...

    24灯十字旋转LED蓝牙版制作资料

    POV系列-24灯十字旋转LED,资料有原理图、PCB丝印图、 改字软件 以及单片机固件,如果有单片机基础完全可以制作参考制作

    大创项目_24.zip

    大学生创业项目源码

    B端安全网关的简单实现#Java#Springboot源码分享

    已实现http协议下的请求转发。支持GET,POST请求以及文件上传,支持IP白名单、apiKey配置。

    【毕业设计】基于uniapp微信小程序电影院选座订票系统设计【源码+论文+答辩ppt+开题报告+任务书】.zip

    【项目资源】:包含前端、后端、移动开发、操作系统、人工智能、物联网、信息化管理、数据库、硬件开发、大数据、课程资源、音视频、网站开发等各种技术项目的源码。包括STM32、ESP8266、PHP、QT、Linux、iOS、C++、Java、MATLAB、python、web、C#、EDA、proteus、RTOS等项目的源码。 【项目质量】:所有源码都经过严格测试,可以直接运行。功能在确认正常工作后才上传。 【适用人群】:适用于希望学习不同技术领域的小白或进阶学习者。可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【附加价值】:项目具有较高的学习借鉴价值,也可直接拿来修改复刻。对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。 【沟通交流】:有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。鼓励下载和使用,并欢迎大家互相学习,共同进步。

    weixin056基于微信小程序的购物系统+php(文档+源码)_kaic

    weixin056基于微信小程序的购物系统+php(文档+源码)_kaic

    使用mingw编译的openssl-3.4.1,有需要的自取吧

    使用mingw编译的openssl-3.4.1,有需要的自取吧

    Oracle19c netca.rsp

    Oracle19c netca.rsp

    前端小白必看!HTML、CSS、JavaScript 基础全解析

    本资源聚焦前端三剑客基础。课程从 HTML 构建网页结构开始,深入 CSS 样式美化,再到 JavaScript 实现交互逻辑。无论你是零基础小白,还是想巩固基础的学习者,都能通过学习,具备搭建静态网页与简单交互页面的能力,轻松迈进前端开发领域。

    Invoke-WmiCommand.zip

    Invoke-WmiCommand

    (转载)五子棋python

    python五子棋 转载的!!!

    基于springboot框架的Javaweb学科竞赛管理系统(完整源码+数据库sql文件+项目文档+Java项目编程实战+编程练手好项目).zip

    关键词:学科竞赛管理,Java语言,MYSQL数据库,Vue框架 摘 要 I ABSTRACT II 1绪 论 1 1.1研究背景 1 1.2设计原则 1 1.3论文的组织结构 2 2 相关技术简介 3 2.1Java技术 3 2.2B/S结构 3 2.3MYSQL数据库 4 2.4Spring Boot框架 4 2.5Vue框架 5 3 系统分析 6 3.1可行性分析 6 3.1.1技术可行性 6 3.1.2操作可行性 6 3.1.3经济可行性 6 3.1.4法律可行性 6 3.2系统性能分析 7 3.3系统功能分析 7 3.4系统流程分析 8 3.4.1注册流程 8 3.4.2登录流程 9 3.4.3添加信息流程 10 4 系统设计 11 4.1系统概要设计 11 4.2系统结构设计 11 4.3 系统顺序图 12 4.4数据库设计 14 4.4.1 数据库实体(E-R图) 14 4.4.2 数据库表设计 16 5 系统的实现 19 5.1学生功能模块的实现 19 5.1.1 学生注册界面 19 5.1.2 学生登录界面 20 5.1.3 赛项详情界面 21 5.1.4 个人中心界

    大创项目go后台.zip

    大学生创业项目源码

    基于Wav2Lip384的AI主播项目整合包

    开源项目整合包 更多内容可以查阅 项目源码搭建介绍: 《我的AI工具箱Tauri+Django开源git项目介绍和使用》https://datayang.blog.csdn.net/article/details/146156817 图形桌面工具使用教程: 《我的AI工具箱Tauri+Django环境开发,支持局域网使用》https://datayang.blog.csdn.net/article/details/141897682

    智慧园区解决方案-16PPT(21页).pptx

    智慧园区,作为未来城市发展的重要组成部分,正逐步从传统园区向智能化、高效化转型。这一转型不仅提升了园区的运营管理水平,更为入驻企业和民众带来了前所未有的便捷与高效。智慧园区的总体设计围绕现状分析、愿景规划、设计理念及六位一体配套展开。传统园区往往面临服务体系不完善、智慧应用面不广、信息资源共享能力不足等问题,而智慧园区则致力于打破这些壁垒,通过物联网技术、大数据分析等手段,构建起一个完整的运营服务体系。这一体系不仅覆盖了企业成长的全周期,还通过成熟的智慧运营经验,为产业集群的发展提供了有力支撑。智慧园区的愿景在于吸引优秀物联网企业和人才入驻,促进产业转型,提高社会经济效应,并为民众打造更安全、高效的智慧生活方式。 在智慧园区的服务体系及配套方面,园区围绕“1+1+1”(学院+创客+基地)、“两中心”(园区指挥中心+金融中心)、“三平台”(成果展示+招商+政府)等核心配套,辅以日常生活各方面的配套,真正实现了从人才培养、研发、转化、孵化、加速到发展的六位一体示范园区。园区服务体系包括园区运营管理体系、企业服务体系和产业社区服务体系。园区运营管理体系通过协同办公、招商推广、产业分析等手段,打破了信息数据壁垒,构建了统一园区运营服务。企业服务体系则提供了共享智能展厅、会议室预定、园区信息服务、办事大厅等一系列便捷服务,助力企业快速成长。产业社区服务体系则更加注重周边生活的便捷性,如物联网成果展示平台、智慧物流、共享创客空间等,为入驻企业和民众提供了全方位的生活配套。这些服务体系不仅提升了园区的整体竞争力,还为入驻企业创造了良好的发展环境。 智慧园区的场景应用更是丰富多彩,涵盖了智慧停车、智慧访客、公共服务、智慧楼宇、智慧物业等多个方面。智慧停车系统通过车牌识别、车位引导、缴费等子系统,实现了停车场的智能化管理,极大提升了停车效率。智慧访客系统则通过预约、登记、识别等手段,确保了园区的安全有序。公共服务方面,智慧照明、智慧监控、智慧充电桩等设施的应用,不仅提升了园区的整体品质,还为民众带来了更加便捷、安全的生活环境。智慧楼宇和智慧物业系统更是通过智能化手段,实现了楼宇和园区的统一化管理,提升了运营效率和居住舒适度。此外,智慧园区还通过O2O平台、医疗系统、综合服务系统等手段,将线上线下资源有机整合,为入驻企业和民众提供了全方位、便捷的服务体验。这些场景应用不仅展示了智慧园区的智能化水平,更为读者提供了丰富的想象空间和实施方案参考。 综上所述,智慧园区作为未来城市发展的重要方向,正以其独特的魅力和优势吸引着越来越多的关注。通过智能化手段的应用和服务体系的完善,智慧园区不仅提升了园区的整体竞争力和运营效率,还为入驻企业和民众带来了前所未有的便捷与高效。对于写方案的读者来说,智慧园区的解决方案不仅提供了丰富的案例参考和实践经验,更为方案的制定和实施提供了有力的支撑和启示。

    成熟STM32直流电压电流采集与检测方案:包含PCB设计、KEIL源码及原理图与详细设计说明,完备STM32直流电压电流采集与检测解决方案:PCB、KEIL源码、原理图、设计说明,lunwen复现新型

    成熟STM32直流电压电流采集与检测方案:包含PCB设计、KEIL源码及原理图与详细设计说明,完备STM32直流电压电流采集与检测解决方案:PCB、KEIL源码、原理图、设计说明,lunwen复现新型扩展移相eps调制,双有源桥dab变器,MATLAB simulink仿真 ,核心关键词:lunwen复现; 新型扩展移相eps调制; 双有源桥dab变换器; MATLAB simulink仿真;,复现新型扩展移相EPS调制:DAB双有源桥变换器在MATLAB Simulink中的仿真研究

    大创项目——考古土方运输车小程序端.zip

    大学生创业项目源码

    清华大学 deepSeek 三部曲全集

    清华大学deepseek三部曲PDF

    蓝桥杯算法实战详解:编程界‘奥林匹克’的技术提升之路

    内容概要:本文介绍了蓝桥杯编程竞赛的历史背景及其重要意义,强调其作为编程领域中‘奥林匹克’的地位。文章全面解析了蓝桥杯中涉及的不同类型的赛题,如数学计算、字符串处理、排序算法、图论算法、动态规划、模拟题等,通过实例详细讲解这些算法的设计思路及其实现方式。还分享了在比赛过程中应掌握的实际技巧,包括如何选择恰当的算法、优化代码性能,以及调试技巧等,旨在全面提升编程能力。 适合人群:对编程感兴趣的在校生及初学者、想要提升编程能力的从业者。 使用场景及目标:帮助读者了解并掌握蓝桥杯的比赛内容和技术要点;培养解决复杂编程问题的能力;激发编程兴趣并为参赛做准备。 其他说明:文中穿插成功案例——小乐同学的经历,展现如何从零基础成长为优秀程序员,并通过自身努力在全国比赛中获奖的例子来鼓励读者积极参与此类活动以提升自我价值。最后号召更多编程爱好者参与到蓝桥杯当中,在实践中锻炼和成长。

    公开整理-上市公司网络财经新闻数据.txt

    因文件较多,数据存放网盘,txt文件内包含下载链接及提取码,永久有效。失效会第一时间进行补充。样例数据及详细介绍参见文章:https://blog.csdn.net/T0620514/article/details/146317475

Global site tag (gtag.js) - Google Analytics