|
lxmxn
版主
积分 11386
发帖 4938
注册 2006-7-23
状态 离线
|
 『楼 主』:
[讨论][共同参与]求1到1000所有素数的和
无聊的时候玩了一把黑客游戏，有一关是一个编程题，题目是求1到1000所有的素数的和，然后加一个sixtoseven.asp就是下一关的地址。
想来自己不会其它的编程语言，于是就用批处理脚本写了一个出来了，但是效率实在是令人不敢恭维，于是放出来让大家也来参与一下，应该用怎样的算法使这个批处理脚本的运行效率提高。如果遇到好的算法，我会酌情加分的，以表鼓励。
我写的代码如下：
@echo %db% off&setlocal enabledelayedexpansion
set t1=%time% %=开始计时=%
set ss=5
%=这里设置5是忽略了2和3，所以这里要加上=%
for /l %%a in (1,2,1000) do (
%=for里面设置步长(step)为2是为了剔除偶数，这样效率可能要高些=%
set /a num=%%a
set /a tc3=!num! "%%" 3
if !tc3! neq 0 (
set /a n=!num!-1
call :sss !n!
if [!flag!]==[bbbb] (echo !num!&set /a ss+=!num!)
)
)
echo 1—1000 中所有的素数加起来的和为: [ %ss% ]%=显示结果=%
set t2=%time%%=计时结束=%
echo/
echo 开始时间:%t1%
echo 结束时间:%t2%
echo/
pause&exit/b0
::::::::::::::::::Sub Function::::::::::::::::::::
:sss
set a=
for /l %%a in (2,1,%1) do (
set /a a=!num! "%%" %%a
if !a! equ 0 (
set flag=aaaa
goto :eof
) else (
set flag=bbbb)
)
|
|
 2007-1-24 11:01 |
|
|
vkill
金牌会员
积分 4103
发帖 1744
注册 2006-1-20
来自 甘肃.临泽
状态 离线
|
『第
2 楼』:
回去想想
[ Last edited by vkill on 2007-1-24 at 11:20 AM ]
|
|
|
2007-1-24 11:18 |
|
|
lxmxn
版主
积分 11386
发帖 4938
注册 2006-7-23
状态 离线
|
『第
3 楼』:
| Quote: | Originally posted by vkill at 2007-1-23 22:18:
回去想想
[ Last edited by vkill on 2007-1-24 at 11:20 AM ] |
|
帖一个网上的解释吧：来自http://sjweb.hhit.edu.cn/article/show.aspx?id=933&cid=71
| Quote: | 素数是这样的整数，它除了能表示为它自己和１的乘积以外，不能表示为任
何其它两个整数的乘积。例如，１５＝３＊５，所以１５不是素数；又如，１２
＝６＊２＝４＊３，所以１２也不是素数。另一方面，１３除了等于１３＊１以
外，不能表示为其它任何两个整数的乘积，所以１３是一个素数。 |
|
|
|
|
2007-1-24 11:24 |
|
|
namejm
荣誉版主
batch fan
积分 5226
发帖 1737
注册 2006-3-10
来自 成都
状态 离线
|
『第
4 楼』:
寻找素数在2005年似乎有了新的方法，这种方法出奇地简单，简单到足以让数学家们警觉起来，请看这篇文章：http://www.irgoc.org/Article/ShowArticle.asp?ArticleID=85。奈何本人不懂那些代码的具体含义，难以转化为批处理来解决，哪位懂得的不妨来转换一下。不过，里面用到了log运算，估计批处理解决起来会相当的麻烦。
另外，lxmxn 在3楼给出的链接中提到了“从2开始，是则留下，不是则去掉”的方法，经过实地演算(仅测试了1～30这个范围的数)，当处理到5这个素数的时候，会去掉19，看来这种方法并不能成立。
[ Last edited by namejm on 2007-1-23 at 11:27 PM ]
|
尺有所短，寸有所长，学好CMD没商量。
考虑问题复杂化，解决问题简洁化。 |
|
|
2007-1-24 12:25 |
|
|
youxi01
高级用户
积分 846
发帖 247
注册 2006-10-27
来自 湖南==》广东
状态 离线
|
|
|
2007-1-24 12:48 |
|
|
lxmxn
版主
积分 11386
发帖 4938
注册 2006-7-23
状态 离线
|
『第
6 楼』:
嗯，效率的确提高了不少，现在平均是5秒左右的时间完成计算，而我的代码要大约18秒。
|
|
|
2007-1-24 12:51 |
|
|
qzwqzw
银牌会员
天的白色影子
积分 2342
发帖 635
注册 2004-3-6
状态 离线
|
『第
7 楼』:
因为在考虑第三种方案
所以这第二种与5楼有些重复
区别仅在于没有在外层循环对３取模
算法的效率没有明显的提高
@echo off&setlocal enabledelayedexpansion
set t1=%time%
set sum=5
for /l %%i in (5,2,2000) do (
set /a limit=%%i / 2
set isPrime=true
for /l %%j in (3,2,!limit!) do (
set /a mod=%%i %% %%j
if "!mod!"=="0" set isPrime=false
)
if "!isPrime!"=="true" (echo %%i&set /a sum+=%%i)
)
echo 1—1000 中所有的素数加起来的和为: [ %sum% ]
echo.
echo 开始时间:%t1%
echo 结束时间:%time%
echo.
pause
|
|
|
2007-1-24 13:57 |
|
|
qzwqzw
银牌会员
天的白色影子
积分 2342
发帖 635
注册 2004-3-6
状态 离线
|
|
|
2007-1-24 14:00 |
|
|
0401
中级用户
带走
积分 435
发帖 88
注册 2005-9-24
状态 离线
|
『第
9 楼』:
很漂亮也，计算速度几乎不受大数的影响。不过一时半刻还看不太懂具体的原理。
|
|
|
2007-1-24 14:14 |
|
|
0401
中级用户
带走
积分 435
发帖 88
注册 2005-9-24
状态 离线
|
『第
10 楼』:
这个算法数越大，速度就越慢。
@echo off
setlocal enabledelayedexpansion
set t=%time%
set s=2 3 5 7 %--1不是素数--%
for /l %%l in (1,1,99) do ( %--从十位开始计算，所以等下要加上2，3，5，7--%
for %%i in (1 3 7 9) do ( %--素数的个位数只能是1，3，7，9--%
set/a m=%%l%%i"%%"3
if !m! neq 0 (
set flag=1
for %%m in (!s!) do ( %--这里用来取余的数是被取余数之前的素数集--% %--ps：我也不清楚这样算对不对--%
set/a b=%%l%%i"%%"%%m
if !b! equ 0 set flag=0
)
) else (set flag=0)
if !flag! equ 1 (
echo %%l%%i
set/a sum+=%%l%%i
set s=!s! %%l%%i
)
)
)
set/a sum=%sum%+2+3+5+7
echo 开始于[%t%]
echo 结束于[%time%]
echo 1000以内的素数和为[%sum%] lxmxn兄的注释很有意思，以前没发觉，我也借来用用，呵呵。
|
|
|
2007-1-24 14:19 |
|
|
youxi01
高级用户
积分 846
发帖 247
注册 2006-10-27
来自 湖南==》广东
状态 离线
|
『第
11 楼』:
如果是纯粹的10000以内，用以下的算法可能要快点（测试时间7秒内）
@echo off&setlocal enabledelayedexpansion
set t1=%time% %=开始计时=%
set sum_=5
echo.>Result.txt
echo 2
echo 3
for /l %%a in (5,2,100) do (
set/a temp=%%a-1
set flag=1
for /l %%b in (3 2 !temp!) do (
set/a num=%%a %% %%b
if !num! EQU 0 set flag=0)
if !flag! EQU 1 (
echo %%a
echo %%a>>Result.txt
set/a sum_+=%%a))
for /l %%a in (101 2 10000) do (
set/a mod=%%a %% 3
if !mod! Neq 0 (
set flag=1
for /f %%i in (Result.txt) do (
set/a mod=%%a %% %%i
if !mod! EQU 0 set flag=0)
if !flag! EQU 1 echo %%a & set/a sum+=%%a))
set/a sum=!sum!+!sum_!
set t2=%time%%=计时结束=%
echo/
echo 开始时间:%t1%
echo 结束时间:%t2%
echo 1000以内的素数和为：%sum%
pause>nul
|
|
|
2007-1-24 22:28 |
|
|
youxi01
高级用户
积分 846
发帖 247
注册 2006-10-27
来自 湖南==》广东
状态 离线
|
『第
12 楼』:
8F的方案中 在循环中 “引用”了 call ，会大大降低效率的！
我的看法是宁愿牺牲一些不必要的数字（比如，在计算101是不是质数时，根据你的意思是没必要算到它能不能被97整除），不过因为可以不使用call，却倒使效率更高（因为纯粹只使用for循环）
[ Last edited by youxi01 on 2007-1-24 at 10:33 PM ]
|
|
|
2007-1-24 22:30 |
|
|
willsion
高级用户
积分 789
发帖 310
注册 2004-9-2
状态 离线
|
『第
13 楼』:
建议版主多搞一些类似的小活动，吸引更多人参与讨论。
因为DOS论坛，基本属于技术性论坛，人气相对较少。
|
|
|
2007-1-24 23:12 |
|
|
lxmxn
版主
积分 11386
发帖 4938
注册 2006-7-23
状态 离线
|
『第
14 楼』:
呵呵，一晚上的时间又有这么多好的算法啊。
特别是qzwqzw兄的第三个方案、0401以及youxi01在11楼的方案，效率都有明显的提高，看来要多花点时间来研究一下算法了，多谢各位的参与，今天加不成分，改天给各位加分鼓励。
|
|
|
2007-1-25 00:25 |
|
|
pengfei
银牌会员
积分 1218
发帖 485
注册 2006-7-21
来自 湖南.娄底
状态 离线
|
『第
15 楼』:
5F先除去奇数和偶数的方法使运行效率提高不少, 11F采用这种去奇偶数再判断的方法, 同时采用临时文件计算大范围的数的效率大大提高.
筛法求素数:
列出要求的所有素数, 然后逐个判断它们是否素数, 找出一个非素数, 就把它挖掉, 最后剩下的就是素数.
算法:
1. 先将1挖掉;
2. 用2去除它后面的各个数, 把能被2整除的数挖掉, 即把2的倍数挖掉.
3. 用3去除它后面各数, 把3的倍数挖掉.
4. 分别用4,5... 各数作为除数去除这些数以后的各数. 直到除数后面的数已被挖掉为止(事实上, 只需进行到除数n的平方根止).
5. 余下的数都为素数.
上面的算法还可以改进, 以提高效率. 批处理中通过构建数组, 完整地实现用筛法求素数.
@echo off
setlocal enabledelayedexpansion
set t=%time%
set sqrt=31
set n=1000
for /l %%i in (1,1,%n%) do set num%%i=%%i
for /l %%i in (2,1,%sqrt%) do (
set /a i=%%i+1
if not "!num%%i!"=="0" (
for /l %%j in (!i!,1,%n%) do (
if not "!num%%j!"=="0" (
set /a x=!num%%j! %% %%i
if "!x!"=="0" set num%%j=0
)
)
)
)
for /l %%i in (2,1,%n%) do (
if not "!num%%i!"=="0" (
set /p =!num%%i!<nul
set /a s+=%%i
)
)
echo.
echo.
echo 1-%n%的素数和=%s%
echo 起始时间=%t%
echo 结束时间=%time%
pause 此代码当处理范围较小时效率比较理想, 我也用C写了一个, 看来C写出来的程序效率的确很高.
附件
1:  prime.rar (2007-1-25 12:21, 4.25 K, 下载附件所需积分 1 点
,下载次数： 10)
|
业精于勤而荒于嬉，形成于思而毁于随。 |
|
|
2007-1-25 04:42 |
|
