中国DOS联盟

-- 联合DOS 推动DOS 发展DOS --
联盟域名：www.cn-dos.net　论坛域名：www.cn-dos.net/forum

游客 | 登录 | 注册 | 会员 | 搜索 | 中国DOS联盟

中国DOS联盟论坛
现在时间是 2026-09-15 12:10

共 47,812 主题排行 / 349,917 发帖 / 今日 0 篇 / 48,268 会员排行

DOS批处理 & 脚本技术（批处理室） » 批处理：素数堆垒及哥德巴赫猜想局部验证

可打印版本　3,498 / 7

第1楼　willsort	发表于 2004-12-06 00:00
元老会员　发帖 1,512　积分 4,432
批处理：素数堆垒及哥德巴赫猜想局部验证 To All: 这个程序是一个批处理程序设计数学问题的一个典型代表，它可以提供给我们一个解决一类问题的方式和方法。源程序来自比利时的一位编程专家，我对它进行了性能上的修改，核心算法思想基本不变。为了便于比较，我将更改的各个版本按顺序贴出，大家基本上可以看到改进一个程序尤其于批处理程序的性能，所能应用的一些方法和技巧。所有的代码版本及性能测试环境可以从此下载。打开附件

第2楼　willsort	发表于 2004-12-06 00:00
元老会员　发帖 1,512　积分 4,432
:: Prime.bat - Generate a serial prime number :: Dirk van Deun - Will Sort Modified 2004/11/18 :: :: 改进: 将源码的所有函数并入主程序中并套了个控制性外壳 :: 效果: 程序文件减少, 运行速度没有明显变化, 测试运行时间超过6分钟 @echo off if == goto %2 if == %comspec% /e:5000 /c %0 $ run goto end:: 对整数 %prime-in% (2 to n) 调用素数判断(prime)进程 :: 若返回真值(素数)则显示此整数, 否则跳过 :run set prime-num= set prime-in=I I :runloop call %0 $ isprime if "%prime-out%"=="true" echo %prime-in% if "%prime-out%"=="true" set prime-num=I%prime-num% if "%prime-num%"=="IIIIIIIIII" goto end set prime-in=I %prime-in% goto runloop:: 对传入的整数 %prime-in% 从n-1到2循环调用除法(divide)函数 :: 若整除则返回假(非素数), 若 %prime-in% 为1则返回真, 否则继续循环除法 :isprime call %0 $ dec %prime-in% :isprimeloop set dividend=%prime-in% set divisor=%dec-out% call %0 $ dec %dec-out% if "%dec-out%"=="" set prime-out=true if "%dec-out%"=="" goto end call %0 $ divide if %div-out%==true set prime-out=false if %div-out%==true goto end call %0 $ dec %divisor% goto isprimeloop:: 对传入的 %dividend%(被除数) %divisor%(除数) 递归调用减法函数 :: 若减为零则返回真(整除), 若下溢则返回假, 否则继续递归减法 :divide if "%dividend%"=="" set div-out=true if "%dividend%"=="" goto end set min-in1=%dividend% set min-in2=%divisor% call %0 $ minus if "%min-err%"=="underflow" set div-out=false if "%min-err%"=="underflow" goto end set dividend=%min-out% %0 $ divide:: 对传入的 %min-in1%(被减数) %min-in2%(减数) 递归调用自减函数 :: 若 %min-in2% 为0则无错返回, 若 %min-in1% 为0则返回下溢错(%min-err%) :: 否则继续递归自减 :minus if "%min-in2%"=="" set min-out=%min-in1% if "%min-in2%"=="" set min-err= if "%min-in2%"=="" goto end if "%min-in1%"=="" set min-err=underflow if "%min-in1%"=="" goto end call %0 $ dec %min-in1% set min-in1=%dec-out% call %0 $ dec %min-in2% set min-in2=%dec-out% %0 $ minus:: 对传入的整数 %3 %4 %5... 进行自减操作 :: 将整数减一后存入 %dec-out% 中返回 :dec set dec-out=%4 :decloop shift if "%4"=="" goto end set dec-out=%dec-out% %4 goto decloop:end

第3楼　willsort	发表于 2004-12-06 00:00
元老会员　发帖 1,512　积分 4,432
:: Prime.bat - Generate a serial prime number :: Dirk van Deun - Will Sort Modified 2004/11/18 :: :: 改进: 将主循环起始值改为3, 步进值改为2, 也即只判断大于2的奇数 :: 效果: 理论上速度应增加一倍, 实际运行时间4分钟多 @echo off if == goto %2 if == %comspec% /e:5000 /c %0 $ run goto end:: 对整数 %prime-in% (3 to n step 2) 调用素数判断(prime)进程 :: 若返回真值(素数)则显示此整数, 否则跳过 :run echo I I set prime-num=I set %prime-num%=I I set prime-in=I I I :runloop call %0 $ isprime if "%prime-out%"=="true" echo %prime-in% if "%prime-out%"=="true" set prime-num=I%prime-num% if "%prime-num%"=="IIIIIIIIII" goto end if "%prime-out%"=="true" set %prime-num%=%prime-in% set prime-in=I I %prime-in% goto runloop:: 对传入的整数 %prime-in% 从n-1到2循环调用除法(divide)函数 :: 若整除则返回假(非素数), 若 %prime-in% 为1则返回真, 否则继续循环除法 :isprime call %0 $ dec %prime-in% :isprimeloop set dividend=%prime-in% set divisor=%dec-out% call %0 $ dec %dec-out% if "%dec-out%"=="" set prime-out=true if "%dec-out%"=="" goto end call %0 $ divide if %div-out%==true set prime-out=false if %div-out%==true goto end call %0 $ dec %divisor% goto isprimeloop:: 对传入的 %dividend%(被除数) %divisor%(除数) 递归调用减法函数 :: 若减为零则返回真(整除), 若下溢则返回假, 否则继续递归减法 :divide if "%dividend%"=="" set div-out=true if "%dividend%"=="" goto end set min-in1=%dividend% set min-in2=%divisor% call %0 $ minus if "%min-err%"=="underflow" set div-out=false if "%min-err%"=="underflow" goto end set dividend=%min-out% %0 $ divide:: 对传入的 %min-in1%(被减数) %min-in2%(减数) 递归调用自减函数 :: 若 %min-in2% 为0则无错返回, 若 %min-in1% 为0则返回下溢错(%min-err%) :: 否则继续递归自减 :minus if "%min-in2%"=="" set min-out=%min-in1% if "%min-in2%"=="" set min-err= if "%min-in2%"=="" goto end if "%min-in1%"=="" set min-err=underflow if "%min-in1%"=="" goto end call %0 $ dec %min-in1% set min-in1=%dec-out% call %0 $ dec %min-in2% set min-in2=%dec-out% %0 $ minus:: 对传入的整数 %3 %4 %5... 进行自减操作 :: 将整数减一后存入 %dec-out% 中返回 :dec set dec-out=%4 :decloop shift if "%4"=="" goto end set dec-out=%dec-out% %4 goto decloop:end

第4楼　willsort	发表于 2004-12-06 00:00
元老会员　发帖 1,512　积分 4,432
:: Prime.bat - Generate a serial prime number :: Dirk van Deun - Will Sort Modified 2004/11/18 :: :: 改进: 判断素数时, 不再除以从2到n-1的所有数, 改为从2到n-1的所有素数 :: 效果: 理论上速度将得到数量级的提升, 测试运行时间约1分钟 @echo off if == goto %2 if == %comspec% /e:5000 /c %0 $ run del ~prime.bat goto end:: 对整数 %prime-in% (3 to n step 2) 调用素数判断(prime)进程 :: 若返回真值(素数)则显示此整数, 否则跳过 :run echo I I set prime-num=I set %prime-num%=I I set prime-in=I I I :runloop call %0 $ isprime if "%prime-out%"=="true" echo %prime-in% if "%prime-out%"=="true" set prime-num=I%prime-num% if "%prime-num%"=="IIIIIIIIII" goto end if "%prime-out%"=="true" set %prime-num%=%prime-in% set prime-in=I I %prime-in% goto runloop:: 将传入的整数 %prime-in% 与已知的所有素数循环相除(调用divide函数) :: 若整除则返回假(非素数), 若 %prime-in% 为1则返回真, 否则继续循环除法 :isprime set divisor-no=I :isprimeloop set dividend=%prime-in% echo set divisor=%%%divisor-no%%%>~prime.bat call ~prime.bat ::echo %prime-in% - %divisor-no% : %dividend% / %divisor% ::pause call %0 $ divide if %div-out%==true set prime-out=false if %div-out%==true goto end if "%divisor-no%"=="%prime-num%" set prime-out=true if "%divisor-no%"=="%prime-num%" goto end set divisor-no=I%divisor-no% goto isprimeloop:: 对传入的 %dividend%(被除数) %divisor%(除数) 递归调用减法函数 :: 若减为零则返回真(整除), 若下溢则返回假, 否则继续递归减法 :divide if "%dividend%"=="" set div-out=true if "%dividend%"=="" goto end set min-in1=%dividend% set min-in2=%divisor% call %0 $ minus if "%min-err%"=="underflow" set div-out=false if "%min-err%"=="underflow" goto end set dividend=%min-out% %0 $ divide:: 对传入的 %min-in1%(被减数) %min-in2%(减数) 递归调用自减函数 :: 若 %min-in2% 为0则无错返回, 若 %min-in1% 为0则返回下溢错(%min-err%) :: 否则继续递归自减 :minus if "%min-in2%"=="" set min-out=%min-in1% if "%min-in2%"=="" set min-err= if "%min-in2%"=="" goto end if "%min-in1%"=="" set min-err=underflow if "%min-in1%"=="" goto end call %0 $ dec %min-in1% set min-in1=%dec-out% call %0 $ dec %min-in2% set min-in2=%dec-out% %0 $ minus:: 对传入的整数 %3 %4 %5... 进行自减操作 :: 将整数减一后存入 %dec-out% 中返回 :dec set dec-out=%4 :decloop shift if "%4"=="" goto end set dec-out=%dec-out% %4 goto decloop:end

第5楼　willsort	发表于 2004-12-06 00:00
元老会员　发帖 1,512　积分 4,432
:: Prime.bat - Generate a serial prime number :: Dirk van Deun - Will Sort Modified 2004/11/18 :: :: 改进: 将除法函数的递归相减算法改为循环相减算法 :: 效果: 代码和call语句减少, 速度提升量与系统相关, 测试运行时间约 2.1s @echo off if == goto %2 if == %comspec% /e:5000 /c %0 $ run del ~prime.bat goto end:: 对整数 %prime-in% (3 to n step 2) 调用素数判断(prime)进程 :: 若返回真值(素数)则显示此整数, 否则跳过 :run echo I I set prime-num=I set %prime-num%=I I set prime-in=I I I :runloop call %0 $ isprime if "%prime-out%"=="true" echo %prime-in% if "%prime-out%"=="true" set prime-num=I%prime-num% if "%prime-num%"=="IIIIIIIIII" goto end if "%prime-out%"=="true" set %prime-num%=%prime-in% set prime-in=I I %prime-in% goto runloop:: 将传入的整数 %prime-in% 与已知的所有素数循环相除(调用divide函数) :: 若整除则返回假(非素数), 若 %prime-in% 为1则返回真, 否则继续循环除法 :isprime set divisor-no=I :isprimeloop set dividend=%prime-in% echo set divisor=%%%divisor-no%%%>~prime.bat call ~prime.bat ::echo %prime-in% - %divisor-no% : %dividend% / %divisor% ::pause call %0 $ divide if %div-out%==true set prime-out=false if %div-out%==true goto end if "%divisor-no%"=="%prime-num%" set prime-out=true if "%divisor-no%"=="%prime-num%" goto end set divisor-no=I%divisor-no% goto isprimeloop:: 对传入的 %dividend%(被除数) %divisor%(除数) 调用循环减法函数 :: 若下溢则返回假, 否则返回真(整除) :divide call %0 $ minus %dividend% set div-out=true if "%min-out%"=="underflow" set div-out=false goto end:: 对传入的 %dividend%(被除数) %divisor%(除数) 循环相减 :: 若不足相减 (%2!=I) 则返回下溢错, 否则直接返回空 :minus ::echo %3 %4 %5 %6 for %%n in (%divisor%) do shift if not == goto minus set min-out= if == set min-out=underflow ::echo min-out: %min-out% ::pause goto end:end

第6楼　willsort	发表于 2004-12-06 00:00
元老会员　发帖 1,512　积分 4,432
:: Prime.bat - Generate a serial prime number :: Dirk van Deun - Will Sort Modified 2004/11/18 :: :: 改进: 将isprime和divided函数并入主函数以及其他一些风格上的改进 :: 效果: 函数,变量和代码均减少, 速度继续提升; 测试运行时间约 1.6秒 @echo off if == goto %2 if == %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 == goto loopminus set min-out= if == set min-out=underflow goto end :end ─────────────────　版务记录　───────────────── 执行：HAT 操作：由于willsort兄贴代码时未使用code标签，论坛解析代码时出现不少错误，现予以修正。 ─────────────────　版务记录　───────────────── [ Last edited by HAT on 2009-4-24 at 12:16 ]

第7楼　willsort	发表于 2004-12-06 00:00
元老会员　发帖 1,512　积分 4,432
:: Prime.bat - Generate a serial prime number :: Dirk van Deun - Will Sort Modified 2004/11/18 :: :: Contents of reference: :: A system of batch files that generates prime numbers in "prisoners :: notation". (It's rather sloooooooow.) END.BAT is really an empty :: file, by the way. :: http://student.vub.ac.be/~dvandeun :: :: 素数堆垒程序修改版: 一个产生素数的程序, 因为其输出形似堆垒而名 :: :: 源代码正如上文所说，非常的慢，所以不得不做了一些修改 :: :: 主要的修改: :: 1 将源码的所有函数并入主程序中, 加套控制性外壳 :: 2 将主循环起始值改为3, 步进值改为2, 也即只判断大于2的奇数 :: 3 判断素数时, 不再除以从2到n-1的所有数, 改为从2到n-1的所有素数 :: 4 将除法函数的递归相减算法改为循环相减算法 :: 5 将素数判断循环和除法循环并入主循环 :: 6 变量名, 标签名, 注释, 缩进等代码风格上的改动 :: :: 环境变量说明: :: iTest:测试数, iPrime:素数序号 :: divisor:用以判断素数的除数, iDivisor:除数序号 :: less: 除法中不足除的标志 :: @echo off if == goto %2 if == %comspec% /e:4096 /c %0 $ init del ~prime.bat goto end:: 初始化: 产生素数2, 将它存为第一个素数, 设置循环起始值为3 :init set iTest=I set iPrime=I set %iPrime%=I I echo I I:: 对3~n的奇数 %iTest% 与已产生的所有素数由小到大循环相除 :: 若全部未整除则显示此整数, 否则递增 %iTest% 后继续循环 :MainLoop set iTest=I I %iTest% set iDivisor=I rimeLoop echo set divisor=%%%iDivisor%%%>~prime.bat call ~prime.bat call %0 $ Divide %iTest% if "%less%"=="" goto MainLoop if "%iDivisor%"=="%iPrime%" goto IsPrime set iDivisor=I%iDivisor% goto PrimeLoop :IsPrime echo %iTest% set iPrime=I%iPrime% if "%iPrime%"=="IIIIIIIIIIII" goto end set %iPrime%=%iTest% goto MainLoop:: 将传入的被除数 %iTest% 除以(循环减)除数 %divisor% :: 若不足除 (无法整除) 则返回不足信号 less, 否则直接返回 ivide for %%n in (%divisor%) do shift if not == goto Divide set less= if == set less=true goto end:end

第8楼　willsort	发表于 2004-12-06 00:00
元老会员　发帖 1,512　积分 4,432
:: Solve.bat - 验证哥德巴赫猜想的程序 :: Will Sort - 2004/11/18 :: :: 从素数堆垒程序变化而来 :: 环境变量说明: :: iTest:测试数, iPrime:素数序号 :: divisor:用以判断素数的除数, iDivisor:除数序号 :: Factor1&Factor2: 偶数的两个分解因子, iFactor1&iFicator2:因子序号 :: less: 除法中不足除的标志, diff: 减法中有差值的标志 :: @echo off if == goto %2 if == %comspec% /e:4096 /c %0 $ init del ~Solve.bat goto end :: 初始化: 产生素数2, 将它存为第一个素数, 设置循环起始值为3 :init set iTest=I I set iPrime=I set %iPrime%=I I :: 对3~n的奇数 %iTest% 与已产生的所有素数由小到大循环相除 :: 若全部未整除则将 %iTest% 存入素数 %iPrime%, 否则跳至 Solve :: 对3~n的偶数 %iTest% 分解为已产生的两个素数之和 :: 若恰好分解则显示此偶数和两个分解因子, 否则继续循环 MainLoop :MainLoop rime - 判断奇数是否为素数 set iTest=I %iTest% set iDivisor=I rimeLoop echo set divisor=%%%iDivisor%%%>~Solve.bat call ~Solve.bat call %0 $ Divide %iTest% if "%less%"=="" goto Solve if "%iDivisor%"=="%iPrime%" goto IsPrime set iDivisor=I%iDivisor% goto PrimeLoop :IsPrime set iPrime=I%iPrime% set %iPrime%=%iTest% :Solve - 将偶数分解为素数之和 set iTest=I %iTest% set iFactor1= :SolveLoop set iFactor1=I%iFactor1% if "%iFactor1%"=="I%iPrime%" goto SolveLoop set iFactor2=%iFactor1% :SolveSubLoop if "%iFactor2%"=="I%iPrime%" goto SolveLoop echo set Factor1=%%%iFactor1%%%>~Solve.bat echo set Factor2=%%%iFactor2%%%>>~Solve.bat call ~Solve.bat call %0 $ Minus %iTest% if "%diff%"=="" goto IsSolve set iFactor2=I%iFactor2% goto SolveSubLoop :IsSolve echo %iTest% echo %Factor1% + %Factor2% if "%iPrime%"=="IIIIIIIII" goto end goto MainLoop :: 将传入的被除数 %iTest% 除以(循环减)除数 %divisor% :: 若不足除 (无法整除) 则返回不足信号 less, 否则直接返回 ivide for %%n in (%divisor%) do shift if not == goto Divide set less= if == set less=true goto end :: 将传入的被减数 %iTest% 减去减数 %Factor1% 和 %Factor2% :: 若有差值 (无法分解) 则返回相差信号 diff, 否则直接返回 :Minus for %%n in (%Factor1%) do shift for %%n in (%Factor2%) do shift set diff= if "%2"=="" set diff=true if not "%3"=="" set diff=true goto end :end ─────────────────　版务记录　───────────────── 执行：HAT 操作：由于willsort兄贴代码时未使用code标签，论坛解析代码时出现不少错误，现予以修正。 ─────────────────　版务记录　───────────────── [ Last edited by HAT on 2009-4-24 at 12:22 ]

[ 联系联盟系统管理团队 - 中国DOS联盟 - 标准版 ]
Sponsored by ifanr Inc | © 2001–2023