中国DOS联盟

回去想想

[ Last edited by vkill on 2007-1-24 at 11:20 AM ]

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

素数是这样的整数，它除了能表示为它自己和１的乘积以外，不能表示为任
何其它两个整数的乘积。例如，１５＝３＊５，所以１５不是素数；又如，１２
＝６＊２＝４＊３，所以１２也不是素数。另一方面，１３除了等于１３＊１以
外，不能表示为其它任何两个整数的乘积，所以１３是一个素数。

　　寻找素数在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 ]

如果纯粹是处理1000以内的数字的话，采用以下的代码可以提高效率：
@echo off&setlocal enabledelayedexpansion set t1=%time% %=开始计时=% echo 2 echo 3 set/a sum=5 for /l %%a in (5,2,1000) do ( set/a temp=%%a %% 3 if !temp! NEQ 0 ( 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)) else set flag=0 if !flag! EQU 1 echo %%a & set/a sum+=%%a) set t2=%time%%=计时结束=% echo/ echo 开始时间:%t1% echo 结束时间:%t2% echo 1000以内的素数和为：%sum% pause>nul

因为在考虑第三种方案

所以这第二种与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 中所有的素数加起来的和为: echo. echo 开始时间:%t1% echo 结束时间:%time% echo. pause

这是第３种方案

仅拿小于所判断数的平方根的质数去除判断数

以缩小比较范围

可以计算到１～１００００的规模

@echo off setlocal enabledelayedexpansion set t1=%time% set sum=5 echo 2 >prime.txt echo 3 >>prime.txt for /l %%i in (5,2,10000) do ( set /a limit=%%i / 2 call :isPrime %%i if "!isPrime!"=="true" ( echo %%i set /a sum+=%%i ) ) echo 1—10000 中所有的素数加起来的和为: %=显示结果=% echo. echo 开始时间:%t1% echo 结束时间:%time% echo. pause goto :eof :isPrime set isPrime=false for /f %%j in (prime.txt) do ( set /a mod=%1 %% %%j if !mod! equ 0 goto :eof set /a prd=%%j * %%j if !prd! geq %1 ( echo %1 >>prime.txt set isPrime=true goto :eof ) )

很漂亮也，计算速度几乎不受大数的影响。不过一时半刻还看不太懂具体的原理。

这个算法数越大，速度就越慢。

@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 开始于 echo 结束于 echo 1000以内的素数和为

lxmxn兄的注释很有意思，以前没发觉，我也借来用用，呵呵。

如果是纯粹的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

8F的方案中 在循环中 “引用”了 call ，会大大降低效率的！
我的看法是宁愿牺牲一些不必要的数字（比如，在计算101是不是质数时，根据你的意思是没必要算到它能不能被97整除），不过因为可以不使用call，却倒使效率更高（因为纯粹只使用for循环）

[ Last edited by youxi01 on 2007-1-24 at 10:33 PM ]

建议版主多搞一些类似的小活动，吸引更多人参与讨论。

因为DOS论坛，基本属于技术性论坛，人气相对较少。

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写出来的程序效率的确很高.