找回密码
 加入
搜索
查看: 36893|回复: 74

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

[复制链接]
发表于 2012-10-27 20:27:19 | 显示全部楼层 |阅读模式
本帖最后由 3mile 于 2012-11-8 17:31 编辑

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

我先给出自己的源码吧.
初始版本如下,这个效率有点低.
游客,如果您要查看本帖隐藏内容请回复


下面这个效率高点
游客,如果您要查看本帖隐藏内容请回复

评分

参与人数 1金钱 +40 收起 理由
Duvet + 40 学习了

查看全部评分

发表于 2012-10-27 22:36:19 | 显示全部楼层
游客,如果您要查看本帖隐藏内容请回复

评分

参与人数 1金钱 +50 收起 理由
3mile + 50 学习了

查看全部评分

发表于 2012-10-27 22:41:19 | 显示全部楼层
本帖最后由 netegg 于 2012-10-27 22:47 编辑

[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]
老外的代码,不过蛋蛋最近脑子秀逗,实在没看明白怎么个道理

评分

参与人数 2金钱 +90 收起 理由
Duvet + 40 学习了
3mile + 50 效率非常高,可惜不是原创

查看全部评分

发表于 2012-10-28 00:00:44 | 显示全部楼层
游客,如果您要查看本帖隐藏内容请回复

赚点金币

评分

参与人数 2金钱 +90 收起 理由
Duvet + 40 学习了
3mile + 50 学习了

查看全部评分

发表于 2012-10-28 04:42:33 | 显示全部楼层
游客,如果您要查看本帖隐藏内容请回复

评分

参与人数 1金钱 +50 收起 理由
3mile + 50 学习了

查看全部评分

发表于 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)

评分

参与人数 2金钱 +40 贡献 +2 收起 理由
Duvet + 40
3mile + 2 学习了,没钱了

查看全部评分

 楼主| 发表于 2012-10-28 10:38:04 | 显示全部楼层
3楼蛋蛋兄的效率非常高,尤其25-30行,很精彩啊.
今天加分已经用完,没加分的兄弟们,明日会补上.
发表于 2012-10-28 10:50:15 | 显示全部楼层
#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)

评分

参与人数 2金钱 +40 贡献 +5 收起 理由
Duvet + 40
3mile + 5 很另类啊.学习了

查看全部评分

发表于 2012-10-29 10:48:02 | 显示全部楼层
看看啥内容
发表于 2012-10-29 23:53:18 | 显示全部楼层
回复 8# shqf


    能说下原理吗?
发表于 2012-10-30 00:20:04 | 显示全部楼层
本帖最后由 zch11230 于 2012-10-30 01:13 编辑

哈哈 上次群里有人在讨论这个问题耶,百度百科重新温习了一下质数写的
游客,如果您要查看本帖隐藏内容请回复

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

评分

参与人数 2金钱 +90 收起 理由
Duvet + 40
3mile + 50 学习了

查看全部评分

发表于 2012-10-30 01:09:56 | 显示全部楼层
回复 1# 3mile


    跟前辈学习了
发表于 2012-10-30 11:54:59 | 显示全部楼层
本帖最后由 1007236046 于 2012-10-30 11:57 编辑

看了下素数的定义,不知这样能否加效率
游客,如果您要查看本帖隐藏内容请回复

评分

参与人数 2金钱 +90 收起 理由
Duvet + 40
3mile + 50 学习了

查看全部评分

发表于 2012-10-30 12:10:07 | 显示全部楼层
回复 10# gto250

这是用正则表达式求得素数,思路也是在网上看到的。稍改了一下,用在AUTOIT中。
先要把每个数如n转换成n个1组成的字串,再用正则表达式去匹配。
这个“\b(11+?)\1+\b”表达式是匹配合数的,取相反的结果就是素数啦。
其中(11+?)是获取11,111,1111,……,\1引用前面匹配到的字串,是判断剩余的字串中是否还存在前面匹配到的字串,如存在就是合数。
发表于 2012-10-30 13:24:23 | 显示全部楼层
看了下素数的定义,不知这样能否加效率
**** 本内容被作者隐藏 ****
1007236046 发表于 2012-10-30 11:54



    setp 2 是个好东西啊  哈哈  加在我写的能减少一半的时间, 加在一楼的也能提高点效率,数字大点能看出来。3楼的没试。。看不懂。
您需要登录后才可以回帖 登录 | 加入

本版积分规则

QQ|手机版|小黑屋|AUTOIT CN ( 鲁ICP备19019924号-1 )谷歌 百度

GMT+8, 2024-3-29 20:14 , Processed in 0.116295 second(s), 36 queries .

Powered by Discuz! X3.5 Licensed

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表