本帖最后由 edisonx 于 2012-11-7 03:56 编辑
回复 17# happytc
happytc 兄太強了，
請教 sBytecode 其實是事先算好的 binary table，
然後呼叫 API 去做顯示動作，請問對嗎？
------------------
To All
初版寫得較慢，100 萬 4 秒才跑得完。
另一版的 code (本文下面會附) ，效率目前應僅次於 17F happytc 兄 ，
附上目前測時，N=100萬，不計輸出時間，執行時間在 5 secs 內之整理。
為避免測時爭議，附上附件。另若覺得不妥，請告知，小弟將刪除。
小弟初版使用的是線性篩法。#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
目前已有現有效率高的演算法可滿足這需求：埃拉托斯特尼篩法。
然後第一份程式碼主要比的不是速度，
而是另一種概念上 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 ? 謝謝。 | 
|手机版|小黑屋|AUTOIT CN
( 鲁ICP备19019924号-1 )谷歌
百度
发表于 2012-11-3 14:17:36
.gif)