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

3mile

坛子最近有点冷清,出个题给大家找点乐子.
枚举N以内的质数(素数),给出源码的都会加分.
效率越高越好.

我先给出自己的源码吧.
初始版本如下,这个效率有点低.

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

下面这个效率高点

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

Duvet

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

netegg

[au3]#include<array.au3>
$aA = _PrimesInRange(199)
_ArrayDisplay($aA)
Func _PrimesInRange($s_max, $s_min = 0)
        Local $max = Int(Abs($s_max)), $min = Int(Abs($s_min)), $res, $a
;        If $min > $max Then _Swap($max, $min)
        If $max > 32000000 Or $max < 4 Then Return SetError(-1, 0, -1)
        $a = _Eratosthenes($max)
        If $min < 3 Then $res = "2*"
        $min = ($min + (Mod($min, 2) = 0) - 3) / 2
        If $min < 0 Then $min = 0
        For $i = $min To UBound($a) - 1
                If $a[$i] = "" Then $res &= 3 + $i * 2 & "*"
        Next
        $res = StringSplit(StringTrimRight($res, 1), "*")
        If $res[1] = "" Then Dim $res[1] = [0]
        Return $res
EndFunc   ;==>_PrimesInRange

Func _Eratosthenes($s_max)
        Local $lim = Ceiling($s_max / 2) - 1, $a[$lim], $max = Int(Sqrt($lim)), $z, $y, $n
        For $i = 0 To $max
                If $a[$i] = 1 Then ContinueLoop
                Dim $z = 3, $y = 3, $n = 3 * $i + 3
                While $n < $lim
                        $a[$n] = 1
                        $z += 2
                        $y += 3
                        $n = $z * $i + $y
                WEnd
        Next
        Return $a
EndFunc   ;==>_Eratosthenes
[/au3]
老外的代码，不过蛋蛋最近脑子秀逗，实在没看明白怎么个道理

1007236046

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

赚点金币

Duvet

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

骗子

最笨的办法,处理越多越慢

Local $hTime = TimerInit()
Local $i = 10000
$jieguo = 1 & @CRLF & 2 & @CRLF
For $j = 3 To $i
        For $jj = 2 To Ceiling ($j/2)
                $biaozhi = '质数'
                If Mod($j, $jj) = 0 Then
                        $biaozhi = '合数'
                        ExitLoop
                EndIf
        Next
        If $biaozhi = '质数' Then $jieguo &= $j & @CRLF
Next
MsgBox(0, '素数' & TimerDiff($hTime), $jieguo)

3mile

3楼蛋蛋兄的效率非常高,尤其25-30行,很精彩啊.
今天加分已经用完,没加分的兄弟们,明日会补上.

shqf

#include <array.au3>
#include <String.au3>
Local $nMax="199", $Primes[1]
For $Number= 2 To $nMax
        If StringRegExp(_StringRepeat("1",$Number),"\b(11+?)\1+\b") =0 Then _ArrayAdd($Primes,$Number)
Next
$Primes[0]=UBound($Primes)-1
_ArrayDisplay($Primes)

menfan1

看看啥内容

gto250

回复 8# shqf


    能说下原理吗？

zch11230

哈哈 上次群里有人在讨论这个问题耶，百度百科重新温习了一下质数写的

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

晕啊 回复后看到上面的 .自己的效率太低下了。

虫子樱桃

回复 1# 3mile


    跟前辈学习了

1007236046

看了下素数的定义，不知这样能否加效率

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

shqf

回复 10# gto250

这是用正则表达式求得素数，思路也是在网上看到的。稍改了一下，用在AUTOIT中。
先要把每个数如n转换成n个1组成的字串，再用正则表达式去匹配。
这个“\b(11+?)\1+\b”表达式是匹配合数的，取相反的结果就是素数啦。
其中(11+?)是获取11，111，1111，……，\1引用前面匹配到的字串，是判断剩余的字串中是否还存在前面匹配到的字串，如存在就是合数。

zch11230

看了下素数的定义，不知这样能否加效率
**** 本内容被作者隐藏 ****
1007236046 发表于 2012-10-30 11:54

    setp 2 是个好东西啊  哈哈  加在我写的能减少一半的时间， 加在一楼的也能提高点效率，数字大点能看出来。3楼的没试。。看不懂。