首先声明一点,文章内容从itpub论坛上看到的,原文链接http://www.itpub.net/thread-1849398-1-1.html,本文主要是记录下笔记,原文中有更详细的分析。使用sql求质素没什么实用价值,重要的是思路。
(一)最简单的方法
思路:将2和所有大于等于3小于XX的奇数取出来,做一中间结果集t。然后逐一校验t中的每个N是否是质数。如果发现一个数字N不能被其他所有数字整除——当然,这些数字要小于等于SQRT(N),那么N就是质数
with t as(select 2 n from dual union select rownum*2+1 from dual connect by rownum<=(10000-2)/2) select count(*) from t a where not exists (select null from t b where b.n<=sqrt(a.n) and mod(a.n, b.n)=0)
最直接的方法,可惜速度最慢。
(二)筛选法
思路:将从2到XX的数都列出来,作为一个全集,然后减去所有的合数,即可得到素数集合
WITH t AS ( SELECT ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= 10000-1) SELECT COUNT(*) FROM (SELECT rn from t MINUS SELECT t1.rn * t2.rn--4=2*2 2*3 9=3*3 3*4 16=4*4 4*5 FROM t t1, t t2 WHERE t1.rn <= t2.rn AND t1.rn <= (SELECT SQRT(10000) FROM DUAL))
(三)改进的筛选法
思路:除了2之外的偶数,可以从全集和合数集中排除
WITH t AS ( --2-10000/2 SELECT ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= 10000/2-1 ) ,t_odd AS ( --奇数 SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= 10000/2-1 ) SELECT COUNT(*) + 1--+2 FROM (SELECT rn from t_odd MINUS SELECT t1.rn * t2.rn FROM t t1, t t2 WHERE t1.rn <= t2.rn AND t1.rn <= (SELECT SQRT(10000) FROM DUAL) AND t1.rn * t2.rn < 10000)
另一种写法:排除偶数
WITH t_odd AS ( SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= 10000/2-1 ) SELECT COUNT(*) + 1 FROM (SELECT rn from t_odd MINUS SELECT t1.rn * t2.rn --9=3*3 3*5 25=5*5 5*7 49=7*7 FROM t_odd t1, t_odd t2 WHERE t1.rn <= t2.rn AND t1.rn <= (SELECT SQRT(10000) FROM DUAL) AND t1.rn * t2.rn < 10000)
(四)逆向exists
with t as(select 2 n from dual union select rownum*2+1 from dual connect by rownum<=(10000-2)/2) , z as (select * from t minus select * from t a where exists (select null from t b where b.n<=sqrt(a.n) and mod(a.n, b.n)=0)) select count(*) from z
或者:
with t as(select rownum*2+1 n from dual connect by rownum<=(10000-2)/2 union select 3 from dual --F5执行计划 走MERGE JOIN ),z as (select * from t minus select * from t a where exists (select null from t b where b.n<=sqrt(a.n) and mod(a.n, b.n)=0)) select count(*)+1 from z
加了union select 3 from dual 之后,执行计划走MERGE JOIN,这一点还没想明白,欢迎指教。
(五)提前剔除奇数
WITH t0 AS ( SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= (10000)/2-1 ), t as(SELECT rn from t0 where mod(rn,3)<>0 and mod(rn,5)<>0 and mod(rn,7)<>0 and mod(rn,11)<>0 and mod(rn,13)<>0 and mod(rn,17)<>0 and mod(rn,19)<>0) SELECT COUNT(*) + 1 + 7 --2,3,5,7,11,13,17,19 FROM (SELECT rn from t MINUS SELECT t1.rn * t2.rn FROM t t1, t t2 WHERE t1.rn <= t2.rn AND t1.rn BETWEEN 9 AND (SELECT SQRT(10000) FROM DUAL) AND t1.rn * t2.rn < 10000)
其实后面的大部分写法都是采用提前筛选掉不合格的数字来减少源数据大小达到加快查询速度。
全文完。
相关推荐
在“sqlPpt借花献佛之作”这个主题中,我们可以期待一个详细讲解SQL的PowerPoint演示文稿,它可能是某位作者整理的关于SQL的学习资料,旨在帮助初学者或有一定基础的学习者深入理解和掌握SQL。 在PowerPoint演示...
在中国高考语文的写作评分标准中,一篇作文的文采斐然往往能够给阅卷老师留下深刻的印象,而其中,巧妙地将古典诗词融入作文之中,不仅能够增色不少,更是展现考生文化素养和语言驾驭能力的重要手段。在2015年的高考...
借花献佛的成语接龙.doc
标题“自治成功的stk500-借花献佛”表明我们即将探讨的是关于STK500开发板在实现自我控制方面取得成功的一个项目或教程。STK500是Atmel公司推出的一种通用的AVR微控制器开发平台,常用于进行AVR系列芯片的编程、调试...
很不错的信息系统工程师考试资料 借花献佛了
### 论文模版-借花献佛大规模 #### 关键知识点提炼: 1. **信息技术与网络技术的发展:** - 20世纪90年代以来,信息技术与网络技术的快速发展成为了全球关注的焦点。 - Internet技术的进步改变了资源获取、拥有...
SAP Router使用方式的详细命令行,以及安装,配置步骤. 文档是SAP的,我借花献佛,给大家参考一下,省去大家找的时间了.
我只是借花献佛。 Flex教程系列之(一) AS3语法——编程基础 http://download.csdn.net/source/1161756 Flex教程系列之(二) AS3语法——流程控制语句 http://download.csdn.net/source/1161804 Flex教程系列之...
我只是借花献佛。 Flex教程系列之(一) AS3语法——编程基础 http://download.csdn.net/source/1161756 Flex教程系列之(二) AS3语法——流程控制语句 http://download.csdn.net/source/1161804 Flex教程系列之...
专业级的网络层讲解,求资深老师讲述,本人借花献佛
图书馆管理系统 本系统为商丘师范学院2008届计算机科学系毕业班赖恩平的毕业设计! 基于C#.net+SQL系统! 安装环境说明: 1:请先从网上下载.NET Framework 2.0运行环境! 2:请安装SQL Server 2000,然后...借花献佛
金蝶K3产品性能稳定性优化指导手册,广大使用者的必备手册,免费下载,借花献佛
结合上面的教程和方法一起使用希望对大家有所帮助,借花献佛了,多谢支持!
相信大家都用得着的一款教程.学过之后应该会有相应的收获.本人也是借花献佛.不准P我...
【中餐礼仪】中,邀请客人参加宴会通常需要一个合适的理由,如开门见山式、借花献佛式或喧宾夺主式。在正式的中式宴会中,座位安排十分讲究,通常按照身份、职务、年龄和性别来确定。主陪位于上座,座位以右为尊,...
09年系统集成工程师试题,借花献佛!大家共享!
佛历软件,谢谢高手的分享,借花献佛,希望大家喜欢。
网上大神的工具,借花献佛,如有侵权,联系删除,谢谢
详细的从入门到精通, 手把手的教你做WEB SERVICE 该资源借花献佛,是一个高手写的,我在这里借花献佛,推广推广,让大家多一个学习的机会,吃水不忘挖井人,轻大家也谢谢写该文档的高手