找回密码
 加入
搜索
楼主: 3mile

[效率算法] 出题:枚举N以内的质数(素数)[已解决]

[复制链接]
发表于 2012-11-3 14:17:36 | 显示全部楼层
又回初中时代了。。。
发表于 2012-11-3 14:33:54 | 显示全部楼层
来看看高效率的  我的计算就不发了  太耗时间
发表于 2012-11-3 20:02:39 | 显示全部楼层
学习思路,我也只能一步一步的算,效率问题考虑不到。。。
发表于 2012-11-3 21:41:11 | 显示全部楼层
回复 17# happytc
强淫呐~~,学习一下!是否能看懂代码。
发表于 2012-11-5 14:47:57 | 显示全部楼层
學習了!!!!
发表于 2012-11-5 19:53:10 | 显示全部楼层
进来看看。以前刚学习qb里,也玩过最基础的。
看来这里高手多。
发表于 2012-11-6 18:42:54 | 显示全部楼层
本帖最后由 runsnake 于 2012-11-6 18:48 编辑

回复 17# happytc


    回复看看代码


天,这个代码效率也太高了,不可思议的地高
可惜,我一点都看不懂,那位高人讲讲这是怎么实现的,原理是什么?

最好是一行行在注释,我真的一点都没有看懂写的啥?
发表于 2012-11-7 01:17:55 | 显示全部楼层

RE: 出题:枚举N以内的质数(素数)

本帖最后由 edisonx 于 2012-11-7 03:56 编辑

回复 17# happytc

happytc 兄太強了,
請教 sBytecode  其實是事先算好的 binary table,
然後呼叫 API 去做顯示動作,請問對嗎?


------------------
To All

初版寫得較慢,100 萬 4 秒才跑得完。
另一版的 code (本文下面會附) ,效率目前應僅次於 17F happytc 兄 ,
附上目前測時,N=100萬,不計輸出時間,執行時間在 5 secs 內之整理。


出题:枚举N以内的质数(素数)

[1] Prime-3F-netegg.au3    3331.174729
[2] Prime-16F-3mile.au3    2988.0624158
[3] Prime-17F-happytc.au3   52.9091249
[4] Prime-39F-edisonx-1.au3    3948.878543
[5] Prime-39F-edisonx-2.au3    1750.200700


為避免測時爭議,附上附件。另若覺得不妥,請告知,小弟將刪除。



小弟初版使用的是線性篩法。
#include<array.au3>
#include <timers.au3>
const  $n = 1000000
; -------------
$cnt = 0.5 * $n
Global $Prime[$cnt] = [2,3]

$begin = _Timer_Init()
$cnt = LinearEratosthenes($n)
$td = _Timer_Diff($begin)
MsgBox(0, "", StringFormat("Find Prime Table Td = %lf msecs, cnt = %d", $td, $cnt))
; _ArrayDisplay($Prime)

; ------------------------------------------
; byEdisonX
Func LinearEratosthenes($n)
        Local $i, $j, $c=2, $gap
        Local $p[$n+1]
           ; Local $end =  Int(Ceiling( Sqrt($n) ))

        $Prime[0] = 2
        $Prime[1] = 3

        $p[0] = 1
        $p[1] = 1
        $p[4] = 1

        $gap = 2
        $i = 5
        While $i < $n
                If Not $p[$i] Then
                        $Prime[$c] = $i
                        $c+=1
                EndIf
                For $j =0 To $c
                        $tmp  = $i * $Prime[$j]
                        If $tmp> $n Then ExitLoop
                        $p[$tmp ] = 1
                Next
                $i += $gap
                $gap = 6 - $gap
        WEnd
        Return $c
EndFunc
我要講的是,由於題目要求的是「小於 N 的所有質數」,
目前已有現有效率高的演算法可滿足這需求:埃拉托斯特尼篩法。

然後第一份程式碼主要比的不是速度,
而是另一種概念上 present,寫的是  埃拉托斯特尼  線性  篩法
也就是每次找到的質數都加到一個質數表中,加速刪除速度,所以上面程式碼一開始就宣告了很大的陣列出來。
( 不過測試出來是沒比較快就是了 )

-------------------

另外 埃拉托斯特尼篩法  還可配合 2n  / 6n  / sqrt 法則,刪除時從 i*i  開始刪 , step 2i 便可 (這前面回覆好像已有提到了)
若還可使用位元運算,會增加 cache hit,速度會更快 ( 但這受限於 AU 語言特性,大概辦不太到吧),
以下演示幾個重點 (1) 只查 6n+-1  (2) 只查到 sqrt(n)  (3) 刪除時從 i*i 開始 ,step 2i
#include<array.au3>
#include <timers.au3>
const  $n = 1000000
; -------------

$begin = _Timer_Init()
$Prime = Eratosthenes6n($n)
$td = _Timer_Diff($begin)
MsgBox(0, "", StringFormat("Find Prime Table Td = %lf msecs", $td))
 _ArrayDisplay($Prime)

; ------------------------------------------
; byEdisonX
Func Eratosthenes6n($n)
        Local $i, $j, $c=2, $gap, $i2
        Local $p[$n+1]
           Local $end =  Int(Ceiling( Sqrt($n) ))

           $gap = 2
        $i = 5
           While $i < $end
                   If Not $p[$i] Then
                           $i2 = $i+$i
                           For $j = $i*$i To $n Step $i2
                                   $p[$j] = 1
                           Next
                   EndIf
                   $i+= $gap
                   $gap = 6 - $gap
           WEnd

        $i = 5
        $gap = 2
        $ret = "2 3 "
        While $i < $n
                If  Not $p[$i] Then $ret &=  $i & " "
                $i += $gap
                $gap = 6 - $gap
        WEnd
        $ret = StringSplit(StringTrimRight($ret, 1), " ")
        return $ret
EndFunc
小弟學淺,其他的就不嘴炮了。
關於質數篩法,有興趣可參考小弟部落格 [C&++] 深入質數 (2/4) - 埃拉托斯特尼篩法
當時做的是 10 億 (用 C 語言實作就是了),約 10 秒完成 ( 其實算是很慢的速度 )。

最後想請教各位,包 code 怎麼 highlight ? 謝謝。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?加入

×

评分

参与人数 1金钱 +80 收起 理由
3mile + 80 精彩

查看全部评分

发表于 2012-11-7 21:44:18 | 显示全部楼层
回复 39# edisonx

請教 sBytecode  其實是事先算好的 binary table,
然後呼叫 API 去做顯示動作,請問對嗎?


肯定不是table了,若算十亿,光存这些素数就得差不多500M才行,你看上面的变量sBytecode的值才多少字节?

其实我的代码里已经用到了你做的第二种‘埃拉托斯特尼篩法’,不过在这基础上用汇编先得到sBytecode后套上字节码筛选。又事先申请一大块内存待用,所以速度才快。


若還可使用位元運算,會增加 cache hit,速度會更快 ( 但這受限於 AU 語言特性,大概辦不太到吧),

不大明白你说的术语,可能是两岸所用术语不一样,但我猜十有八九我用的就是上面你所说的!

评分

参与人数 1贡献 +5 收起 理由
3mile + 5 很棒的见解

查看全部评分

发表于 2012-11-7 22:04:15 | 显示全部楼层
回复 40# happytc


    謝謝 happytc 您的細心解說。

   另所謂的位元運算,指的是 bitwise hacker,抱歉我沒注意到兩岸的名詞有些差異,下次會注意,附上英文,最後謝謝您不吝分享這麼神奇的程式碼,受益良多 :)

评分

参与人数 1金钱 +20 收起 理由
3mile + 20 我很赞同

查看全部评分

发表于 2013-3-9 06:56:05 | 显示全部楼层
向各位前辈学习
发表于 2013-3-9 11:01:36 | 显示全部楼层
用了3楼的脚本,把值调到10000000,跑了好多分钟,耗内存到284M,算出有664579个质数,最大的质数是9999991

数学上是有最大质数这一说的吧?
发表于 2013-3-9 13:51:30 | 显示全部楼层
来看看 学习学习
发表于 2013-3-11 17:48:52 | 显示全部楼层
酷!好!棒!
发表于 2013-3-15 19:40:59 | 显示全部楼层
收藏了。谢谢楼主分享
您需要登录后才可以回帖 登录 | 加入

本版积分规则

QQ|手机版|小黑屋|AUTOIT CN ( 鲁ICP备19019924号-1 )谷歌 百度

GMT+8, 2024-3-29 15:42 , Processed in 0.072798 second(s), 15 queries .

Powered by Discuz! X3.5 Licensed

© 2001-2024 Discuz! Team.

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