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 begin
复制代码

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

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 :eof
复制代码

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

lhjoanna

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