强淫呐~~，学习一下！是否能看懂代码。 學習了!!!!{:face (356):} 进来看看。以前刚学习qb里，也玩过最基础的。
看来这里高手多。 本帖最后由 runsnake 于 2012-11-6 18:48 编辑
回复 17# happytc
回复看看代码
天，这个代码效率也太高了，不可思议的地高
可惜，我一点都看不懂，那位高人讲讲这是怎么实现的，原理是什么？
最好是一行行在注释，我真的一点都没有看懂写的啥？
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以内的质数(素数)
Prime-3F-netegg.au3 3331.174729
Prime-16F-3mile.au3 2988.0624158
Prime-17F-happytc.au3 52.9091249
Prime-39F-edisonx-1.au3 3948.878543
Prime-39F-edisonx-2.au3 1750.200700
為避免測時爭議，附上附件。另若覺得不妥，請告知，小弟將刪除。
小弟初版使用的是線性篩法。#include<array.au3>
#include <timers.au3>
const$n = 1000000
; -------------
$cnt = 0.5 * $n
Global $Prime[$cnt] =
$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 = 2
$Prime = 3
$p = 1
$p = 1
$p = 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
IfNot $p[$i] Then $ret &=$i & " "
$i += $gap
$gap = 6 - $gap
WEnd
$ret = StringSplit(StringTrimRight($ret, 1), " ")
return $ret
EndFunc
小弟學淺，其他的就不嘴炮了。
關於質數篩法，有興趣可參考小弟部落格 深入質數 (2/4) - 埃拉托斯特尼篩法
當時做的是 10 億 (用 C 語言實作就是了)，約 10 秒完成 ( 其實算是很慢的速度 )。
最後想請教各位，包 code 怎麼 highlight ? 謝謝。 回复 39# edisonx
請教 sBytecode其實是事先算好的 binary table，
然後呼叫 API 去做顯示動作，請問對嗎？
肯定不是table了，若算十亿，光存这些素数就得差不多500M才行，你看上面的变量sBytecode的值才多少字节？
其实我的代码里已经用到了你做的第二种‘埃拉托斯特尼篩法’，不过在这基础上用汇编先得到sBytecode后套上字节码筛选。又事先申请一大块内存待用，所以速度才快。
若還可使用位元運算，會增加 cache hit，速度會更快 ( 但這受限於 AU 語言特性，大概辦不太到吧)，
不大明白你说的术语，可能是两岸所用术语不一样，但我猜十有八九我用的就是上面你所说的！ 回复 40# happytc
謝謝 happytc 您的細心解說。
另所謂的位元運算，指的是 bitwise hacker，抱歉我沒注意到兩岸的名詞有些差異，下次會注意，附上英文，最後謝謝您不吝分享這麼神奇的程式碼，受益良多 :) 向各位前辈学习 用了3楼的脚本，把值调到10000000，跑了好多分钟，耗内存到284M，算出有664579个质数，最大的质数是9999991
数学上是有最大质数这一说的吧？ 来看看 学习学习 酷！好！棒！ 收藏了。谢谢楼主分享