ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

快捷登录

搜索
EH技术汇-专业的职场技能充电站 妙哉!函数段子手趣味讲函数 Excel服务器-会Excel,做管理系统 Excel Home精品图文教程库
HR薪酬管理数字化实战 Excel 2021函数公式学习大典 Excel数据透视表实战秘技 打造核心竞争力的职场宝典
300集Office 2010微视频教程 数据工作者的案头书 免费直播课集锦 ExcelHome出品 - VBA代码宝免费下载
用ChatGPT与VBA一键搞定Excel WPS表格从入门到精通 Excel VBA经典代码实践指南
楼主: 香川群子

[原创] 跟我学算法 【初级篇】:求某个整数范围内所有素数

  [复制链接]

TA的精华主题

TA的得分主题

 楼主| 发表于 2015-1-29 17:04 | 显示全部楼层
以上算法原理,就是数学上有名的【筛子法筛选素数】

即,在某个2-N范围内,仅需使用所有 2-Sqr(N)范围内的最小素数,
对整个2-N数据范围内进行标记,筛掉那些 最小素数的整数倍的合数,
最后剩下来的一定是>Sqr(N)的素数了。


部分筛选后剩余素数的效果图如下:
(仅保留奇数部分,因为不用说,所有偶数对能被2整除,所以不可能是素数)

说到这里,我想留个作业给大家:
目前的记录合数状态的数组a定义为
ReDim a(1 To n) As Boolean
因此是包含所有偶数的。

问题:如何写代码改进算法,毫不费力地排除所有偶数? 这样代码的速度效率肯定可以提的更高!

Pic.png

TA的精华主题

TA的得分主题

 楼主| 发表于 2015-1-29 17:31 | 显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册
Zamyi 发表于 2015-1-29 16:39
以为多高明,比近四年前的帖子还差许多!
http://club.excelhome.net/thread-697413-4-1.html 38楼

你有更好的改进过的算法代码吗?

…………
我手里速度最快的代码,比你四年前的代码速度快 19倍。(计算1000时)

计算  1万时,比你的快40倍。
计算  5万时,比你的快55倍。
计算 10万时,比你的快64倍。
计算100万时,比你的快103倍。

以上均不含输出。呵呵

TA的精华主题

TA的得分主题

 楼主| 发表于 2015-1-29 17:38 | 显示全部楼层
本帖最后由 香川群子 于 2015-1-29 17:41 编辑
Zamyi 发表于 2015-1-29 16:43
哈哈,只能说数学还差。第一点,排除偶数,第二点,只需检查Sqrt(n)的质数就行。

其实本帖30楼的代码test5,就已经比你四年前的代码速度快了 10-20倍了。呵呵呵呵。
而且排除偶数的大招还没用呢……但是,根本的算法关键已经出炉
……数组循环步长直接标记,免除了Mod算法。这个真的是重大改进之处。呵呵。

TA的精华主题

TA的得分主题

发表于 2015-1-29 20:53 | 显示全部楼层

TA的精华主题

TA的得分主题

发表于 2015-1-29 22:15 | 显示全部楼层
本帖最后由 weechau 于 2015-1-30 00:06 编辑

只算奇数 只能用能不能整除来判断了吧?

TA的精华主题

TA的得分主题

发表于 2015-1-30 07:35 | 显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册
来挺老师讲解了。。

TA的精华主题

TA的得分主题

发表于 2015-1-30 08:24 | 显示全部楼层

TA的精华主题

TA的得分主题

发表于 2015-1-30 08:43 | 显示全部楼层
香川群子 发表于 2015-1-29 17:38
其实本帖30楼的代码test5,就已经比你四年前的代码速度快了 10-20倍了。呵呵呵呵。
而且排除偶数的大招还 ...

第一,帖子不是我的;
第二,比四年前快,那是必须的;
第三,资源问题,n*(4+2)/(n*0.2*4)=7.5,是人家资源的7.5倍,对于海量数据,也不得不考虑。

TA的精华主题

TA的得分主题

发表于 2015-1-30 09:30 | 显示全部楼层
香川群子 发表于 2015-1-29 17:04
以上算法原理,就是数学上有名的【筛子法筛选素数】

即,在某个2-N范围内,仅需使用所有 2-Sqr(N)范围内 ...

群子的算法讲解很精彩。依然按你的思路仅从效率而言,还有一小块地方可以优化哦。就是sqr(n) 这里,我们知道sqr 是vba 内置的开方函数,但是sqr本身是用c++ 语言编写按照泰勒展开公式求平方的,这对系统的开销是相对比较大的。即在sqr 内部也会有循环等等,只不过对vb 程序员封装起来了。(当然这块的前沿是卡马克算法求平方根,号称史上最快的算法,但是vba 的库函数不是这种方法来实现的。这是C 的另一个话题,我们这里就打住)
我们既然知道sqr (c 当中是sqrt) 的效率和开销是比较大的,用什么方法来提高效率呢?
如果i <= sqr(n) 那么一定 i*i <=n
这样很简单的我们就把一个需要开方的算法转换成一个乘法了,对系统开销降低了不少。我们知道乘法相对简单,在底层实际上是转换成加法实现的,而加法器其实是硬件实现的。
我们测试过(其实还没有使用筛法,两个程序都是普通的循环mod 判断),用乘法实现的程序比调用开方库函数的程序在较大的数据区域,比如1-1000000000 效率提高接近10%。

最后提一句卡马克算法,俺的数学一向不咋的,没看太明白。是他的求平方根算法,是把数字乘以一个卡马克常数,然后就得出精度相当高的平方根值了。如果采用这种方法实现的sqr 函数,那么求平方根的速度是可能比转换成乘法的算法思路不遑多让的。群子数学基础很赞,有兴趣可以研究一下。百度上相关说明很多。

评分

3

查看全部评分

TA的精华主题

TA的得分主题

发表于 2015-1-30 09:34 | 显示全部楼层
Zamyi 发表于 2015-1-30 08:43
第一,帖子不是我的;
第二,比四年前快,那是必须的;
第三,资源问题,n*(4+2)/(n*0.2*4)=7.5,是人家 ...

这是算法大O 阶的问题了,呵呵。
评价,无非就是时间效率和空间效率,现在貌似都更考虑时间效率更多一些,比较现在的存储介质比起以前大大的丰富了。非专业的数学渣(比如俺)想学这块知识真是非常困难,严蔚敏教授的课程看的我想自杀。
您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

手机版|关于我们|联系我们|ExcelHome

GMT+8, 2024-3-29 09:26 , Processed in 0.050478 second(s), 8 queries , Gzip On, Redis On.

Powered by Discuz! X3.4

© 1999-2023 Wooffice Inc.

沪公网安备 31011702000001号 沪ICP备11019229号-2

本论坛言论纯属发表者个人意见,任何违反国家相关法律的言论,本站将协助国家相关部门追究发言者责任!     本站特聘法律顾问:李志群律师

快速回复 返回顶部 返回列表