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

lxzzr

批处理验证哥得巴赫猜想

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

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

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


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


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

batman

效率不高，先发了：

@echo off&setlocal enabledelayedexpansion
set /p a=请输入一个大于6的偶数：
for /l %%a in (2,1,%a%) do set /a b=%%a/2+1&call :lp %%a
set "str=#2#%str%"
echo 1-%a%中所有的素数为：%str:#=%
for %%a in (%str%) do (
    set "var=!str: %%a=!"
    for %%b in (!var!) do (
        set "d=%%a"&set "d=!d:#=!"
        set "e=%%b"&set "e=!e:#=!"
        set /a num=d+e
        if %a% equ !num! echo %a%=!d!+!e!&goto next
    )
)
:next
pause>nul&goto :eof
:lp
for /l %%a in (2,1,%b%) do (
    set /a c=%1%%%%a
    if !c! equ 0 goto :eof
)
set str=%str% #%1#COPY

思路：
    先获取2-输入的偶数中的所有素数，然后再对素数进行两两相加，如和等于输入数就输出结果。

[ 本帖最后由 batman 于 2009-4-24 22:41 编辑 ]

lhjoanna

先构造素数表，感觉用批来构造素数表效率很低啊，哪位高手如果能用位来实现就好了。
我也来写一个，先构造素数表，效率问题，只构造了10000以内的。

@echo off&setlocal enabledelayedexpansion
echo.&echo 正在构建素数表(只第一次需要)，请耐心等待(10-20s)...
for /l %%i in (3 2 100) do (
    if not defined .%%i ( 
       set /a n=%%i*%%i
       for /l %%j in (!n! %%i 10000) do if not defined .%%j set .%%j=0
    )
)
:begin
echo.&set /p even=请输入大于6的偶数:
set /a n=even/2
echo.&echo The result:
for /l %%i in (2 1 !n!) do (
    set /a "p=%%i,q=even-p"
    if not defined .%%i (
       if not defined .!q! echo !even!=%%i+!q!
    )
)
goto beginCOPY

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

xxx

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

inittab

也发一个，效率是个大问题。数字越大速度几何级下降。

@echo off&setlocal enabledelayedexpansion
cls
:begin
set/p var=请输入大于6的偶数(q退出):
if "%var%"=="q" (goto :eof)
set/a 1/var 2>nul || goto begin
set/a yn=var%%2
if !var! lss 6 (goto begin) else if !yn! neq 0 (goto begin)
 
set/a var0=var/2
for /l %%i in (3,1,!var0!) do (
set /a num1=%%i,num2=var-num1
 
call :lp !num1!
if !ok!==yes (call :lp !num2!)
if !ok!==yes (echo !var!=!num1!+!num2!)
)
 
goto begin
 
 
 
:lp
set ok=yes
for /l %%x in (2,1,!var0!) do (
if %1 gtr %%x (
set/a tt=%1 %% %%x
if !tt! equ 0 (set ok=no&goto :eof)
)
)COPY

Batcher

【转帖1】批处理实现素数堆垒及哥德巴赫猜想局部验证

:: Prime.bat - Generate a serial prime number
:: Dirk van Deun - Will Sort Modified 2004/11/18
::
:: 改进: 将isprime和divided函数并入主函数以及其他一些风格上的改进
:: 效果: 函数,变量和代码均减少, 速度继续提升; 测试运行时间约 1.6秒
@echo off
if [%1]==[$] goto %2
if [%1]==[] %comspec% /e:5000 /c %0 $ init
del ~prime.bat
goto end
:: 初始化: 产生素数2, 将它存为第一个素数, 设置循环起始值
:init
echo I I
set prime-num=I
set %prime-num%=I I
set prime-in=I
:: 对3~n的奇数 %prime-in% 与已产生的所有素数由小到大循环相除
:: 若全部未整除则显示此整数, 否则递增 %prime-in% 后继续循环 
:runloop
set prime-in=I I %prime-in%
set divisor-no=I
    :divideloop
    echo set divisor=%%%divisor-no%%%>~prime.bat
    call ~prime.bat
    call %0 $ loopminus %prime-in%
    if "%min-out%"=="" goto runloop
    if "%divisor-no%"=="%prime-num%" goto isprime
    set divisor-no=I%divisor-no%
    goto divideloop
:isprime
echo %prime-in%
set prime-num=I%prime-num%
if "%prime-num%"=="IIIIIIIIII" goto end
set %prime-num%=%prime-in%
goto runloop
:: 对传入的 %dividend%(被除数) %divisor%(除数) 循环相减
:: 若不足相减 (%2!=I) 则返回下溢错, 否则直接返回空
:loopminus
for %%n in (%divisor%) do shift
if not [%3]==[] goto loopminus
set min-out=
if [%2]==[] set min-out=underflow
goto end
:endCOPY

原文地址：http://www.cn-dos.net/forum/viewthread.php?tid=14580

Batcher

【转帖2】批处理筛选质数

@echo off
setlocal enabledelayedexpansion
::::::::::::::::::::::::::::Find Prime Numbers::::::::::::::::::::::::::::
::::::::::::::::::::::::::::{s11ss  2007-9-20}::::::::::::::::::::::::::::
:r
echo Please input the upper limit number:
set /p n=
if not !n! geq 2 (echo 2 at least. & goto :r)
echo.
echo Calculating...
set /a i=2
for /l %%a in (2,1,!n!) do (
        set m%%a=0
)
:ci
set /a j=!i!
:cj
set /a m=!i!*!j!
if !m! leq !n! (
        set /a j+=1
        set m!m!=1
        goto :cj
) else (
        set /a i+=1
        set /a ii=!i!*!i!
        if !ii! leq !n! (goto :ci) else (goto :e)
)
:e
set /a counter=0
echo.
echo In [2,!n!],prime numbers are:
for /l %%a in (2,1,!n!) do (
        if !m%%a! equ 0 (
                echo %%a
                set /a counter+=1
                )
)
echo.
echo In total:!counter!
echo.
echo Press Any Key To Exit.
pause>nulCOPY

原文地址：http://www.cn-dos.net/forum/viewthread.php?tid=33724

Batcher

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

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

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

1000以内测试没有漏检
1000~46400 没有测试

@echo off
setlocal EnableDelayedExpansion
 
:loop_test
set testnum=
set /p testnum=请输入一个整数(按i使用内置测试集，直接按回车退出): 
if "%testnum%"=="" goto :eof
if /i not "%testnum%"=="i" (
    call :JudgePrime %testnum%
    if errorlevel 2 (echo 无效输入：%testnum%
    ) else if errorlevel 1 (echo %testnum% 是素数
    ) else (echo %testnum% 是合数)
    goto :loop_test
)
 
set time0=%time%
for /l %%i in (46001,2,48000) do (
    set /a testnum=%%i
    call :JudgePrime !testnum!
    if !errorlevel! equ 1 set /p=!testnum!  <nul & set /a iprime+=1
)
echo.
echo.
echo found: %iprime%
echo begin: %time0%
echo finish: %time%
pause
goto :eof
 
:JudgePrime
if [%1]==[] exit /b 2
set /a tmp1=%1
if not %tmp1%==%1 exit /b 2
if %1 lss 2 exit /b 0
if %1 equ 2 exit /b 1
 
set i=0
for %%i in (2,3,5,7,11) do (
   set prime_!i!=%%i
   set /a prime6p_!i!=%%i*%%i*%%i
   set /a prime6p_!i!*=prime6p_!i!
   set /a i+=1
)
 
set i=0
:loop1_JP
call set prime_i=%%prime_%i%%%
call set prime6p_i=%%prime6p_%i%%%
if %1 geq %prime6p_3% (
    if !prime_i! equ 3 (
        set /a i+=1
        goto :loop1_JP
    ) 
) else (
    if !prime_i! neq 2 if %1 lss !prime6p_i! exit /b 1    
)
call :LikePrime %1 %prime_i%
if not errorlevel 1 exit /b 0
set /a i+=1
if %i% lss 5 goto :loop1_JP
exit /b 1
goto :eof
 
:LikePrime
set /a x=result=1, tmp1=%1-1, bits=0
 
:loop1_LP
set /a bits+=1
set /a "tmp1>>=1" 
if %tmp1% gtr 0 goto :loop1_LP
 
set /a tmp1=%1-1
:loop2_LP
set /a bits-=1
set /a result=(x*x) %% %1  %=此句代码判断导致大素数时数据溢出=%
if %result% equ 1 if %x% neq 1 if %x% neq %tmp1% exit /b 0
set /a "tmp2=%tmp1% & (1 << %bits%)"
if %tmp2% neq 0 set /a result=(result*%2) %% %1
set x=%result%
if %bits% gtr 0 goto :loop2_LP
if %result% equ 1 exit /b 1
goto :eofCOPY

原文地址：http://www.cn-dos.net/forum/viewthread.php?tid=27198

batman

来个高效点的：

@echo off&setlocal enabledelayedexpansion
set /p a=请输入一个大于6的偶数：
for /l %%a in (3,1,%a%) do (
    set /a b=a-%%a,n=0&call :lp %%a !b!
    if !n! equ 2 echo %a%=%%a+!b!&goto next
)
:next
pause>nul&goto :eof 
:lp
set /a c=%1/2+1
for /l %%a in (2,1,%c%) do (
    set /a d=%1%%%%a
    if !d! equ 0 goto :eof
)
set /a n+=1
if "%2" neq "" shift&goto lpCOPY

随风

batcher 发的都看不懂啊，效率高的惊人。。。
以下是把batman的代码略改算法，效率有所提升

@echo off&setlocal enabledelayedexpansion
set /a a=1000000
call :loop
pause&goto :eof 
:loop
set /a f=a/2
for /l %%a in (3,2,%f%) do (
    set /a b=a-%%a,n=0&call :lp %%a !b!
    if !n! equ 2 echo  %a%=%%a+!b!&goto :eof
)
goto :eof 
:lp
set /a c=%1/2
for /l %%a in (3,2,%c%) do (
    set /a d=%1%%%%a
    if !d! equ 0 goto :eof
)
set /a n+=1
if "%2" neq "" shift&goto lpCOPY

[ 本帖最后由 随风 于 2009-4-25 12:57 编辑 ]

batman

修改我楼上的，用位运算取得数的平方根近似值，以减少循环次数：

@echo off&setlocal enabledelayedexpansion
rem write by batman on 2009-4-25 15:51 of bbs.bathome.net
set /p a=请输入一个大于6的偶数：
set "t=%time:~,-3%"
for /l %%a in (3,2,%a%) do (
    set /a b=a-%%a,n=0&call :lp %%a !b!
    if !n! equ 2 (
       echo 开始时间：%t% 结束时间：!time:~,-3!
       echo %a%=%%a+!b!&goto next
    )
)
:next
pause>nul&goto :eof 
:lp
for /l %%a in (1,1,30) do (
     set /a "num=2<<%%a",yu=%%a%%2
     if %%a equ 30 set /a "num=~num"
     if !num! geq %1 set /a "c=2<<%%a/2+yu"&goto loop
)
:loop
for /l %%a in (3,2,%c%) do (
     if %%a neq %1 set /a d=%1%%%%a
     if !d! equ 0 goto :eof
)
set /a n+=1
if "%2" neq "" shift&goto lpCOPY

lhjoanna

采用位运算构造素数表，具体思路：比如构造10000以内的素数表，就用10000/32个变量来表示这10000个数的状态，每一个数都有32位，用每一位表示一种状态，1表示是素数，0表示非素数，这样就可以省下32倍的空间。比如判断1000是否为素数，就看第1000/32个变量的第1000%32位是否为1。
     经测试，采用位运算比上面直接用10000个变量定义构造素数表节省了2-3倍的时间。但是对于再大点儿的数时间还是很大，我想这是批处理的局限吧。在C编译器上测试，用c代码位操作构造素数表，1亿以内的素数表构造也不到1秒。

@echo off&setlocal enabledelayedexpansion
echo.&echo 正在构建素数表(只第一次需要)，请耐心等待(3-4s)...
for /l %%a in (0 1 313) do set /a .%%a=0xFFFFFFFF
for /l %%i in (2 1 100) do (
    set /a "p=%%i/32,q=1<<(%%i%%32)"
    set /a "n=.!p!&q"
    if !n! neq 0 (
       set /a i=%%i,n=%%i*%%i
       for /l %%j in (!n! !i! 10000) do (
           set /a "p=%%j/32,q=1<<(%%j%%32)"
           set /a ".!p!&=~q"
       )
    )
)
:begin
 echo.&set /p even=请输入大于6的偶数:
 set /a n=even/2
 echo.&echo The result:
 for /l %%i in (2 1 !n!) do (
    set /a "p=%%i,q=even-p"
    call :check !p!
    if !c! neq 0 (
       call :check !q!
       if !c! neq 0 echo !even!=%%i+!q!
    )
 )
 goto begin
 
:check
 set /a "a=%1/32,b=1<<(%1%%32)"
 set /a "c=.!a!&b"
 goto :eofCOPY

附：一开始我感觉32位的有符号数只能使用31位，因为最高位位符号位，后又想，符号位并不影响素数的判断，最高位即使为1，说明了此变量为负数，同时也说明了这一位状态的对应的数为素数，并不矛盾。

batman

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

[ 本帖最后由 batman 于 2009-4-25 17:55 编辑 ]

inittab

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

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

lhjoanna

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