3mile 发表于 2012-10-27 20:27:19

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

本帖最后由 3mile 于 2012-11-8 17:31 编辑

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

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

下面这个效率高点
**** Hidden Message *****

Duvet 发表于 2012-10-27 22:36:19

**** Hidden Message *****

netegg 发表于 2012-10-27 22:41:19

本帖最后由 netegg 于 2012-10-27 22:47 编辑

#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 = "" Then Dim $res =
        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

老外的代码，不过蛋蛋最近脑子秀逗，实在没看明白怎么个道理

1007236046 发表于 2012-10-28 00:00:44

**** Hidden Message *****
赚点金币

Duvet 发表于 2012-10-28 04:42:33

**** Hidden Message *****

骗子 发表于 2012-10-28 05:48:29

本帖最后由 骗子 于 2012-10-28 05:57 编辑

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

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 发表于 2012-10-28 10:38:04

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

shqf 发表于 2012-10-28 10:50:15

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

menfan1 发表于 2012-10-29 10:48:02

看看啥内容

gto250 发表于 2012-10-29 23:53:18

回复 8# shqf


    能说下原理吗？

zch11230 发表于 2012-10-30 00:20:04

本帖最后由 zch11230 于 2012-10-30 01:13 编辑

哈哈 上次群里有人在讨论这个问题耶，百度百科重新温习了一下质数写的
**** Hidden Message *****
晕啊 回复后看到上面的 .自己的效率太低下了。

虫子樱桃 发表于 2012-10-30 01:09:56

回复 1# 3mile


    跟前辈学习了

1007236046 发表于 2012-10-30 11:54:59

本帖最后由 1007236046 于 2012-10-30 11:57 编辑

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

shqf 发表于 2012-10-30 12:10:07

回复 10# gto250

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

zch11230 发表于 2012-10-30 13:24:23

看了下素数的定义，不知这样能否加效率
**** 本内容被作者隐藏 ****
1007236046 发表于 2012-10-30 11:54 http://www.autoitx.com/images/common/back.gif


    setp 2 是个好东西啊哈哈加在我写的能减少一半的时间， 加在一楼的也能提高点效率，数字大点能看出来。3楼的没试。。看不懂。
页: [1] 2 3 4 5
查看完整版本: 出题:枚举N以内的质数(素数)[已解决]