[新手上路]批处理新手入门导读[视频教程]批处理基础视频教程[视频教程]VBS基础视频教程[批处理精品]批处理版照片整理器
[批处理精品]纯批处理备份&还原驱动[批处理精品]CMD命令50条不能说的秘密[在线下载]第三方命令行工具[在线帮助]VBScript / JScript 在线参考
返回列表 发帖

[出题]批处理验证哥得巴赫猜想

批处理验证哥得巴赫猜想

哥得巴赫猜想:任何一个大于6的偶数都是两个素数之和.

素数:就是在所有比1大的整数中,除了1和它本身以外,不再有别的因数.

偶数:自然数中,能被2整除的数是偶数,反之是奇数.


题:输入任何一个大于6的偶数,将其表示为两个素数之和.


注:DOS联盟论坛有相关的参考资料和贴子。

效率不高,先发了:
  1. @echo off&setlocal enabledelayedexpansion
  2. set /p a=请输入一个大于6的偶数:
  3. for /l %%a in (2,1,%a%) do set /a b=%%a/2+1&call :lp %%a
  4. set "str=#2#%str%"
  5. echo 1-%a%中所有的素数为:%str:#=%
  6. for %%a in (%str%) do (
  7.     set "var=!str: %%a=!"
  8.     for %%b in (!var!) do (
  9.         set "d=%%a"&set "d=!d:#=!"
  10.         set "e=%%b"&set "e=!e:#=!"
  11.         set /a num=d+e
  12.         if %a% equ !num! echo %a%=!d!+!e!&goto next
  13.     )
  14. )
  15. :next
  16. pause>nul&goto :eof
  17. :lp
  18. for /l %%a in (2,1,%b%) do (
  19.     set /a c=%1%%%%a
  20.     if !c! equ 0 goto :eof
  21. )
  22. set str=%str% #%1#
复制代码
思路:
    先获取2-输入的偶数中的所有素数,然后再对素数进行两两相加,如和等于输入数就输出结果。

[ 本帖最后由 batman 于 2009-4-24 22:41 编辑 ]
***共同提高***

TOP

先构造素数表,感觉用批来构造素数表效率很低啊,哪位高手如果能用位来实现就好了。
我也来写一个,先构造素数表,效率问题,只构造了10000以内的。
  1. @echo off&setlocal enabledelayedexpansion
  2. echo.&echo 正在构建素数表(只第一次需要),请耐心等待(10-20s)...
  3. for /l %%i in (3 2 100) do (
  4.     if not defined .%%i (
  5.        set /a n=%%i*%%i
  6.        for /l %%j in (!n! %%i 10000) do if not defined .%%j set .%%j=0
  7.     )
  8. )
  9. :begin
  10. echo.&set /p even=请输入大于6的偶数:
  11. set /a n=even/2
  12. echo.&echo The result:
  13. for /l %%i in (2 1 !n!) do (
  14.     set /a "p=%%i,q=even-p"
  15.     if not defined .%%i (
  16.        if not defined .!q! echo !even!=%%i+!q!
  17.     )
  18. )
  19. goto begin
复制代码

[ 本帖最后由 lhjoanna 于 2009-4-24 23:16 编辑 ]

TOP

嗯...还是只能停留在试的层次啊~

TOP

也发一个,效率是个大问题。数字越大速度几何级下降。
  1. @echo off&setlocal enabledelayedexpansion
  2. cls
  3. :begin
  4. set/p var=请输入大于6的偶数(q退出):
  5. if "%var%"=="q" (goto :eof)
  6. set/a 1/var 2>nul || goto begin
  7. set/a yn=var%%2
  8. if !var! lss 6 (goto begin) else if !yn! neq 0 (goto begin)
  9. set/a var0=var/2
  10. for /l %%i in (3,1,!var0!) do (
  11. set /a num1=%%i,num2=var-num1
  12. call :lp !num1!
  13. if !ok!==yes (call :lp !num2!)
  14. if !ok!==yes (echo !var!=!num1!+!num2!)
  15. )
  16. goto begin
  17. :lp
  18. set ok=yes
  19. for /l %%x in (2,1,!var0!) do (
  20. if %1 gtr %%x (
  21. set/a tt=%1 %% %%x
  22. if !tt! equ 0 (set ok=no&goto :eof)
  23. )
  24. )
复制代码

TOP

【转帖1】批处理实现素数堆垒及哥德巴赫猜想局部验证
  1. :: Prime.bat - Generate a serial prime number
  2. :: Dirk van Deun - Will Sort Modified 2004/11/18
  3. ::
  4. :: 改进: 将isprime和divided函数并入主函数以及其他一些风格上的改进
  5. :: 效果: 函数,变量和代码均减少, 速度继续提升; 测试运行时间约 1.6秒
  6. @echo off
  7. if [%1]==[$] goto %2
  8. if [%1]==[] %comspec% /e:5000 /c %0 $ init
  9. del ~prime.bat
  10. goto end
  11. :: 初始化: 产生素数2, 将它存为第一个素数, 设置循环起始值
  12. :init
  13. echo I I
  14. set prime-num=I
  15. set %prime-num%=I I
  16. set prime-in=I
  17. :: 对3~n的奇数 %prime-in% 与已产生的所有素数由小到大循环相除
  18. :: 若全部未整除则显示此整数, 否则递增 %prime-in% 后继续循环
  19. :runloop
  20. set prime-in=I I %prime-in%
  21. set divisor-no=I
  22.     :divideloop
  23.     echo set divisor=%%%divisor-no%%%>~prime.bat
  24.     call ~prime.bat
  25.     call %0 $ loopminus %prime-in%
  26.     if "%min-out%"=="" goto runloop
  27.     if "%divisor-no%"=="%prime-num%" goto isprime
  28.     set divisor-no=I%divisor-no%
  29.     goto divideloop
  30. :isprime
  31. echo %prime-in%
  32. set prime-num=I%prime-num%
  33. if "%prime-num%"=="IIIIIIIIII" goto end
  34. set %prime-num%=%prime-in%
  35. goto runloop
  36. :: 对传入的 %dividend%(被除数) %divisor%(除数) 循环相减
  37. :: 若不足相减 (%2!=I) 则返回下溢错, 否则直接返回空
  38. :loopminus
  39. for %%n in (%divisor%) do shift
  40. if not [%3]==[] goto loopminus
  41. set min-out=
  42. if [%2]==[] set min-out=underflow
  43. goto end
  44. :end
复制代码
原文地址:http://www.cn-dos.net/forum/viewthread.php?tid=14580
我帮忙写的代码不需要付钱。如果一定要给,请在微信群或QQ群发给大家吧。
【微信公众号、微信群、QQ群】http://bbs.bathome.net/thread-3473-1-1.html
【支持批处理之家,加入VIP会员!】http://bbs.bathome.net/thread-67716-1-1.html

TOP

【转帖2】批处理筛选质数
  1. @echo off
  2. setlocal enabledelayedexpansion
  3. ::::::::::::::::::::::::::::Find Prime Numbers::::::::::::::::::::::::::::
  4. ::::::::::::::::::::::::::::{s11ss  2007-9-20}::::::::::::::::::::::::::::
  5. :r
  6. echo Please input the upper limit number:
  7. set /p n=
  8. if not !n! geq 2 (echo 2 at least. & goto :r)
  9. echo.
  10. echo Calculating...
  11. set /a i=2
  12. for /l %%a in (2,1,!n!) do (
  13.         set m%%a=0
  14. )
  15. :ci
  16. set /a j=!i!
  17. :cj
  18. set /a m=!i!*!j!
  19. if !m! leq !n! (
  20.         set /a j+=1
  21.         set m!m!=1
  22.         goto :cj
  23. ) else (
  24.         set /a i+=1
  25.         set /a ii=!i!*!i!
  26.         if !ii! leq !n! (goto :ci) else (goto :e)
  27. )
  28. :e
  29. set /a counter=0
  30. echo.
  31. echo In [2,!n!],prime numbers are:
  32. for /l %%a in (2,1,!n!) do (
  33.         if !m%%a! equ 0 (
  34.                 echo %%a
  35.                 set /a counter+=1
  36.                 )
  37. )
  38. echo.
  39. echo In total:!counter!
  40. echo.
  41. echo Press Any Key To Exit.
  42. pause>nul
复制代码
原文地址:http://www.cn-dos.net/forum/viewthread.php?tid=33724
我帮忙写的代码不需要付钱。如果一定要给,请在微信群或QQ群发给大家吧。
【微信公众号、微信群、QQ群】http://bbs.bathome.net/thread-3473-1-1.html
【支持批处理之家,加入VIP会员!】http://bbs.bathome.net/thread-67716-1-1.html

TOP

【转帖3】批处理寻找大素数-32位正整数的素性判定

以下代码完全照搬了以下链接中的判定算法——米勒拉宾检验+二次检验
http://blog.csdn.net/bsrw/archive/2006/11/28/1419145.aspx

遗憾的是其中的二次检测会导致大素数判定时数据溢出
测试结果从46400开始大量出现因为数据溢出而导致的漏检

1000以内测试没有漏检
1000~46400 没有测试
  1. @echo off
  2. setlocal EnableDelayedExpansion
  3. :loop_test
  4. set testnum=
  5. set /p testnum=请输入一个整数(按i使用内置测试集,直接按回车退出):
  6. if "%testnum%"=="" goto :eof
  7. if /i not "%testnum%"=="i" (
  8.     call :JudgePrime %testnum%
  9.     if errorlevel 2 (echo 无效输入:%testnum%
  10.     ) else if errorlevel 1 (echo %testnum% 是素数
  11.     ) else (echo %testnum% 是合数)
  12.     goto :loop_test
  13. )
  14. set time0=%time%
  15. for /l %%i in (46001,2,48000) do (
  16.     set /a testnum=%%i
  17.     call :JudgePrime !testnum!
  18.     if !errorlevel! equ 1 set /p=!testnum!  <nul & set /a iprime+=1
  19. )
  20. echo.
  21. echo.
  22. echo found: %iprime%
  23. echo begin: %time0%
  24. echo finish: %time%
  25. pause
  26. goto :eof
  27. :JudgePrime
  28. if [%1]==[] exit /b 2
  29. set /a tmp1=%1
  30. if not %tmp1%==%1 exit /b 2
  31. if %1 lss 2 exit /b 0
  32. if %1 equ 2 exit /b 1
  33. set i=0
  34. for %%i in (2,3,5,7,11) do (
  35.    set prime_!i!=%%i
  36.    set /a prime6p_!i!=%%i*%%i*%%i
  37.    set /a prime6p_!i!*=prime6p_!i!
  38.    set /a i+=1
  39. )
  40. set i=0
  41. :loop1_JP
  42. call set prime_i=%%prime_%i%%%
  43. call set prime6p_i=%%prime6p_%i%%%
  44. if %1 geq %prime6p_3% (
  45.     if !prime_i! equ 3 (
  46.         set /a i+=1
  47.         goto :loop1_JP
  48.     )
  49. ) else (
  50.     if !prime_i! neq 2 if %1 lss !prime6p_i! exit /b 1   
  51. )
  52. call :LikePrime %1 %prime_i%
  53. if not errorlevel 1 exit /b 0
  54. set /a i+=1
  55. if %i% lss 5 goto :loop1_JP
  56. exit /b 1
  57. goto :eof
  58. :LikePrime
  59. set /a x=result=1, tmp1=%1-1, bits=0
  60. :loop1_LP
  61. set /a bits+=1
  62. set /a "tmp1>>=1"
  63. if %tmp1% gtr 0 goto :loop1_LP
  64. set /a tmp1=%1-1
  65. :loop2_LP
  66. set /a bits-=1
  67. set /a result=(x*x) %% %1  %=此句代码判断导致大素数时数据溢出=%
  68. if %result% equ 1 if %x% neq 1 if %x% neq %tmp1% exit /b 0
  69. set /a "tmp2=%tmp1% & (1 << %bits%)"
  70. if %tmp2% neq 0 set /a result=(result*%2) %% %1
  71. set x=%result%
  72. if %bits% gtr 0 goto :loop2_LP
  73. if %result% equ 1 exit /b 1
  74. goto :eof
复制代码
原文地址:http://www.cn-dos.net/forum/viewthread.php?tid=27198
我帮忙写的代码不需要付钱。如果一定要给,请在微信群或QQ群发给大家吧。
【微信公众号、微信群、QQ群】http://bbs.bathome.net/thread-3473-1-1.html
【支持批处理之家,加入VIP会员!】http://bbs.bathome.net/thread-67716-1-1.html

TOP

来个高效点的:
  1. @echo off&setlocal enabledelayedexpansion
  2. set /p a=请输入一个大于6的偶数:
  3. for /l %%a in (3,1,%a%) do (
  4.     set /a b=a-%%a,n=0&call :lp %%a !b!
  5.     if !n! equ 2 echo %a%=%%a+!b!&goto next
  6. )
  7. :next
  8. pause>nul&goto :eof
  9. :lp
  10. set /a c=%1/2+1
  11. for /l %%a in (2,1,%c%) do (
  12.     set /a d=%1%%%%a
  13.     if !d! equ 0 goto :eof
  14. )
  15. set /a n+=1
  16. if "%2" neq "" shift&goto lp
复制代码
***共同提高***

TOP

batcher 发的都看不懂啊,效率高的惊人。。。
以下是把batman的代码略改算法,效率有所提升
  1. @echo off&setlocal enabledelayedexpansion
  2. set /a a=1000000
  3. call :loop
  4. pause&goto :eof
  5. :loop
  6. set /a f=a/2
  7. for /l %%a in (3,2,%f%) do (
  8.     set /a b=a-%%a,n=0&call :lp %%a !b!
  9.     if !n! equ 2 echo  %a%=%%a+!b!&goto :eof
  10. )
  11. goto :eof
  12. :lp
  13. set /a c=%1/2
  14. for /l %%a in (3,2,%c%) do (
  15.     set /a d=%1%%%%a
  16.     if !d! equ 0 goto :eof
  17. )
  18. set /a n+=1
  19. if "%2" neq "" shift&goto lp
复制代码

[ 本帖最后由 随风 于 2009-4-25 12:57 编辑 ]
技术问题请到论坛发帖求助!

TOP

修改我楼上的,用位运算取得数的平方根近似值,以减少循环次数:
  1. @echo off&setlocal enabledelayedexpansion
  2. rem write by batman on 2009-4-25 15:51 of bbs.bathome.net
  3. set /p a=请输入一个大于6的偶数:
  4. set "t=%time:~,-3%"
  5. for /l %%a in (3,2,%a%) do (
  6.     set /a b=a-%%a,n=0&call :lp %%a !b!
  7.     if !n! equ 2 (
  8.        echo 开始时间:%t% 结束时间:!time:~,-3!
  9.        echo %a%=%%a+!b!&goto next
  10.     )
  11. )
  12. :next
  13. pause>nul&goto :eof
  14. :lp
  15. for /l %%a in (1,1,30) do (
  16.      set /a "num=2<<%%a",yu=%%a%%2
  17.      if %%a equ 30 set /a "num=~num"
  18.      if !num! geq %1 set /a "c=2<<%%a/2+yu"&goto loop
  19. )
  20. :loop
  21. for /l %%a in (3,2,%c%) do (
  22.      if %%a neq %1 set /a d=%1%%%%a
  23.      if !d! equ 0 goto :eof
  24. )
  25. set /a n+=1
  26. if "%2" neq "" shift&goto lp
复制代码
2

评分人数

    • lxzzr: 高,我的代码都不敢贴出来了PB + 10 技术 + 1
    • 随风: 确实高效。PB + 20 技术 + 1
***共同提高***

TOP

采用位运算构造素数表,具体思路:比如构造10000以内的素数表,就用10000/32个变量来表示这10000个数的状态,每一个数都有32位,用每一位表示一种状态,1表示是素数,0表示非素数,这样就可以省下32倍的空间。比如判断1000是否为素数,就看第1000/32个变量的第1000%32位是否为1。
     经测试,采用位运算比上面直接用10000个变量定义构造素数表节省了2-3倍的时间。但是对于再大点儿的数时间还是很大,我想这是批处理的局限吧。在C编译器上测试,用c代码位操作构造素数表,1亿以内的素数表构造也不到1秒。
  1. @echo off&setlocal enabledelayedexpansion
  2. echo.&echo 正在构建素数表(只第一次需要),请耐心等待(3-4s)...
  3. for /l %%a in (0 1 313) do set /a .%%a=0xFFFFFFFF
  4. for /l %%i in (2 1 100) do (
  5.     set /a "p=%%i/32,q=1<<(%%i%%32)"
  6.     set /a "n=.!p!&q"
  7.     if !n! neq 0 (
  8.        set /a i=%%i,n=%%i*%%i
  9.        for /l %%j in (!n! !i! 10000) do (
  10.            set /a "p=%%j/32,q=1<<(%%j%%32)"
  11.            set /a ".!p!&=~q"
  12.        )
  13.     )
  14. )
  15. :begin
  16. echo.&set /p even=请输入大于6的偶数:
  17. set /a n=even/2
  18. echo.&echo The result:
  19. for /l %%i in (2 1 !n!) do (
  20.     set /a "p=%%i,q=even-p"
  21.     call :check !p!
  22.     if !c! neq 0 (
  23.        call :check !q!
  24.        if !c! neq 0 echo !even!=%%i+!q!
  25.     )
  26. )
  27. goto begin
  28. :check
  29. set /a "a=%1/32,b=1<<(%1%%32)"
  30. set /a "c=.!a!&b"
  31. goto :eof
复制代码
附:一开始我感觉32位的有符号数只能使用31位,因为最高位位符号位,后又想,符号位并不影响素数的判断,最高位即使为1,说明了此变量为负数,同时也说明了这一位状态的对应的数为素数,并不矛盾。

TOP

应该我楼上的效率到了极限了。。。。如此我认为,再怎么高效地构建素数表,都只是做了无用功。

[ 本帖最后由 batman 于 2009-4-25 17:55 编辑 ]
***共同提高***

TOP

原帖由 lhjoanna 于 2009-4-25 12:59 发表
采用位运算构造素数表,具体思路:比如构造10000以内的素数表,就用10000/32个变量来表示这10000个数的状态,每一个数都有32位,用每一位表示一种状态,1表示是素数,0表示非素数,这样就可以省下32倍的空间。比如判 ...


太厉害了。对移位运算和逻辑运算还不太明白。先下来收藏

TOP

Re:batman
     呵,就此题来说,兄的代码确实能够比较高效的解决。我想如果能从这道题目挖掘出什么更深层的问题,那也就是素数的构建了。因为对素数的研究有许多的实际意义,比如数论、密码技术等。这也是一个公认的难题,如何在有限的空间进行更高效的求解素数。比如输出1-1亿内所有的素数,或者一个文件中包含成千上万个大数要判定是否为素数。为了把判定效率降低到线性水平,不可能对每一个数进行从头判断,构建素数表是必要的选择了。

TOP

返回列表