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

3mile

回复 15# zch11230
嗯,有道理哦.
我再试下还能不能提高点效率.

#include<array.au3>
Local $time = TimerInit()
Local $2nd = 1000000

Local $out = "2" & @CRLF

Local $Array[$2nd + 1]
For $i = 3 To $2nd Step 2
        $Array[$i] = True
Next

For $i = 0 To $2nd
        If $Array[$i] Then
                $out &= $i & @CRLF
                For $n = $i * $i To UBound($Array) - 1 Step $i
                        $Array[$n] = False
                Next
        EndIf
Next

$out_arr = StringSplit(StringTrimRight($out, 1), @CRLF, 1)
_ArrayDisplay($out_arr, "用时:" & TimerDiff($time))

happytc

回复 16# 3mile


    前面都是回复可见呀，不知道前面的效率怎么样?
等这个帖子回复了，看看前面的达人方法。
这种嘛，用字节码筛选法，几乎不用计算，再先申请一块内存，那个效率还不是吼吼的呀，给个一到一百万中的素数计算的，看看速度呀：我的老爷机子，计算1000000里的素数就只需要100毫秒！

当然主要想挣“三笑”的钱！

游客，如果您要查看本帖隐藏内容请回复

seniors

只来学习,没代码,不会

3mile

回复 18# seniors
兄台谦虚了.

duck904

怎么都隐藏啊

3mile

回复 17# happytc

happytc兄很牛啊.
呵呵,这钱给得值.

Qokelate

不懂的路过，顺便看看各位源码

user3000

断网3天, 没赶上'盛会' 啊.

游客，如果您要查看本帖隐藏内容请回复

主要回复一下,学习学习!

xiehuahere

思来想去，只有笨办法，就不拿出来了。
进来学习。

zch11230

我勒个去 17楼的 计算1亿都只需要6秒，是我1万倍的效率啊。

小影

学习一下老大们的方法，我的老方法就不发源码了

happytc

回复  happytc

happytc兄很牛啊.
呵呵,这钱给得值.
3mile 发表于 2012-10-30 17:24

    呵，一般这类计算，就是要“不计算”效率才高，只要一计算，无论你修改多好的算法，都会随着着N的增大，时间复杂度和空间复杂度都会正比例增大（还好，不是几何级数增涨）。

象下面这种，就耗时了

$iMaxNum = 1000000
$hInit = TimerInit()
$sPrimes = PrimeNumCalc($iMaxNum)
$iTimer = TimerDiff($hInit)

MsgBox(0,"计算耗时", "计算" & $iMaxNum & "内的所有素数共耗时：" & $iTimer & " 毫秒")
MsgBox(0,"素数",$sPrimes)


Func PrimeNumCalc($iN)
    Local $p[$iN + 1], $i, $j, $z, $n
        
    For $z = 3 To $iN Step 2
        $p[$z] = 1
    Next
    For $i = 3 To Sqrt($iN) Step 2
        If $p[$i] And Mod($p[$i], 2) Then
            For $j = $i * $i To $iN Step $i
                $p[$j] = 0
            Next
            $n &= $i & " "
        EndIf
    Next
    If Not Mod($i, 2) Then $i += 1
    For $z = $i To $iN Step 2
        If $p[$z] Then $n &= $z & " "
    Next
    Return "2 " & $n
EndFunc 

lixiaolong

来学习了，最近没时间玩autoit，手痒了~

yangdai

厲害
學習了

1007236046

回复 27# happytc
这个改成step 2*$i 也能提效率