首先声明一点,文章内容从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借花献佛之作,介绍的挺详细,相信对于学习有很大帮助
2015高考语文满分作文36计之借花献佛:巧用诗词增文采素材
比较全的Oracle函数及其简单说明,作为日常开发的一个参考!也是从网上下载的,借花献佛!
阿南的ARM入门调试笔记,很详细很不错的东东。有他一步一步的调试过程和遇到的问题的详细笔记。。借花献佛了。。
一个项目涉及到的50个Sql语句,整理的大乌龟同学的代码,借花献佛。
借花献佛的成语接龙.doc
很不错的信息系统工程师考试资料 借花献佛了
这本笔记整合了小弟参加java培训的所有课程的笔记,不过作者是小弟的学长,个人觉得还不错,如果你是初学者,我觉得这个就是为你量身打造的!所以也就借花献佛一下,希望跟大家分享一下
什么嘛,要点积分还要做这么多事,真讨厌,真讨厌,讨厌死了。。。。讨厌得很。哼!
自治成功的stk500 电路图 源程序 HEX
一个关于开关电源的设计过程范例,主要是针对反激式开关电源的设计,对于设计人员的开发具有相当的参考价值
不使用API读写INI文件,借花献佛。。。
使用单片机发送彩信的代码,借花献佛。错误之处望指正
exp/imp导出导入工具的使用手册,我也是在别处找的资料,借花献佛
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,然后...借花献佛