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