中国DOS联盟

此帖的由来

http://www.cn-dos.net/forum/viewthread.php?tid=27044

-----------------------------------------------------------------------------------------------

以下代码完全照搬了以下链接中的判定算法——米勒拉宾检验+二次检验

http://blog.csdn.net/bsrw/archive/2006/11/28/1419145.aspx

-----------------------------------------------------------------------------------------------

遗憾的是其中的二次检测会导致大素数判定时数据溢出

测试结果从46400开始大量出现因为数据溢出而导致的漏检

1000以内测试没有漏检

1000~46400 没有测试

@echo off

setlocal EnableDelayedExpansion

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 begin: %time0%

echo finish: %time%

echo found: %iprime%

pause

goto :eof



:JudgePrime

if == 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 :eof

[ Last edited by qzwqzw on 2007-1-28 at 11:34 AM ]

顶～～欣赏～～～

qzwqzw兄的代码精彩~~~ 支持!

由于批处理中set /a进行算术运算时可以存储的最大值为长整型(32 位), 正数为2147483647, 负数为-2147483648. 再多加或减1时都会溢出.

批处理进行大数判定时效率还是很慢, 可以单独判定一个数是否素数, 这样能更好地讨论一些算法的实现.

实际上顶楼的代码实现的就是单个大素数的判定

代码中的循环只是用来判断其算法的有效性

而代码的效率可以通过从语法上的改善来提高

--------------------------------------------------
关于整型溢出的上下界是受cmd本身的限制

不仅仅是set/a而已

要想解决数据溢出的问题

一是寻找不使用二次检验的确定性判定算法

二是构建cmd处理64位整数的能力

这可能是我们讨论的主要方向

---------------------------------------------------

也许用64位Windows的CMD也可以解决

不知谁有测试环境可以测试一下

建议兄做成一个让用户自己输入一个数, 再判断该数是否为素数.

此代码效率很差, 只是演示.

@echo off

setlocal enabledelayedexpansion

set /p num=请输入一个数:

echo 判断中, 请稍等...

set t=%time%

set /a sqrt=num/2,form=1

for /l %%i in (2 1 %sqrt%) do (

    set /a x=!num! %% %%i

    if "!x!"=="0" set form=0&goto show

)

:show

echo.

if "%form%"=="1" (echo %num%是素数.) else (echo %num%不是素数.)

echo 起始时间=%t%

echo 结束时间=%time%

pause

由于批处理中不能计算一个数的平方根, 这里用除2代替.

[ Last edited by pengfei on 2007-1-29 at 04:45 AM ]

感觉用户输入没有什么大用

较小的数都已测试过

较大的数是素数的概率比较低

测试的效率很低

-------------------------------------
不过也好

就加上一个输入判断

如果输入i则使用内置测试集判定素数

否则进行单个素数的判定

@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 == 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 :eof

我的建议是先采集判断方法,然后再代码化.

对一个素数的判定,我的方法是:
--------------
条件1.
任一个>2的自然数,%%10 NEQ 1\3\7\9 为合数.

条件2.
不符合条件1的,能被小于其平方根的任意质数整除为合数.

不符合条件1.2的为质数.
-------------------
此方法的最大缺点是要计算"小于被测试数平方根的所有质数"

不过此方法可以保存一份自小至大的质数表,在多次次检测时可以显著提高效率

尤其当"后次检测在前任一次检测范围内",效率更高.

关于批处理中无法计算平方根的问题,可以变通一下.在枚举过程中,利用IF语句进行控制.

例如:我下面代码中 :MAIN 段中 IF...ELSE...

@ECHO %DBG% OFF

SETLOCAL ENABLEDELAYEDEXPANSION



SET /P X=请输入大于2的自然数：

CALL :PRI 2



:MAIN

FOR /L %%i IN (3,2,%X%) DO CALL :ANA %%i

EXIT /B                            



:ANA

FOR %%j IN (!STR!) DO (

                       SET /A K=%%j*%%j

                       IF !K! GTR %1 (

                                      CALL :PRI %1 & GOTO :EOF

                                      ) ELSE (

                                              SET /A T=%1%%%%j & IF !T! EQU 0 GOTO :EOF

                                              )

                       )

GOTO :EOF



:PRI

SET STR=!STR! %1 & ECHO %1

GOTO :EOF

这段代码,2.7/512 配置 ,在X=10万 时效率尚可,时间为:
开始: 16:10:48.95
结束: 16:14:01.56

[ Last edited by qjbm on 2007-1-29 at 04:17 PM ]

编辑中有删除本帖的功能，可以试试

判定算法在顶楼给的链接里有讨论

你所给出的算法中对10的取模倒是很有创意

但给数时通常步进值取2

所以判断时可以不考虑0/2/4/6/8的尾数

而5是素数表中第三个素数

很快就会被试除法用来做判定

因此节约的性能可能很有限

另外请注意

这里主要探讨单个32位正整数的素性判定

素数表的方法通常用于判定一个素数群

而且理论上说

如果要判定一个最大的32位正整数是否正整数

你的算法（实际上以前也讨论过这些算法）要构建的素数表就太大了

大约需要四千多个素数才能通过试除法判定

而且你的生成素数表的算法并没有优化

即没有到sqrt(n)就停止生成素数

素数表会大很多

系统环境空间明显是不够用的

[ Last edited by qzwqzw on 2007-1-29 at 05:09 PM ]

在8楼的代码中,由于批处理无法进行sqrt(n)计算

所以使用了:

SET /A K=%%j*%%j

IF !K! GTR %1 GOTO :EOF 

进行控制,相当于到sqrt(n)就停止.

不过此种方法还是试除法.没有质的突破.

关于:
米勒-拉宾法加二次检测后所有的最小可判定底数都不大于n^(1/6)仍然只是一个

猜想,无法证明.我也曾利用试除法,对50万以内素数进行各种处理以寻找规律,

但都是在一定范围内有效....不能完全公式化..唔...可以公式化就留名青史了...:)

可以以此贴收集众家之长,说不定自然数素性判定法公式就在本贴产生.

[ Last edited by qjbm on 2007-1-29 at 06:11 PM ]

关于8楼代码也许我理解的有误

IF !K! GTR %1 GOTO :EOF

感觉它只是控制试除的上界

而非生成素数的上界

比如判断一个整数7是否素数

素数表只需要生成到3就可以了

而你的素数表会生成到5

虽然它只会试除到3

所以在显示完是否素数后

应该再加一个判断

看是否需要将这个素数追加到到素数表

这个优化在顶楼提到了链接里已经有间接的实现了

------------------------------------------------

我是没奢望能讨论出新的判定公式了

只希望能将现有的算法代码化并能在有效的时间内得出结果

毕竟这里能讨论算法的人很少

能讨论数论的人更是罕见

你的理解没有太大误差,

在被判断的自然数为质数时,被枚举素数表上限确实多一个.但不对其进行试除.

但是在被判断的自然数为合数时,是不到上限即可断定,

SET /A T=%1%%%%j & IF !T! EQU 0 GOTO :EOF

枚举到整除就断定.

我建议不要在对8楼的代码进行讨论,因为只是一个试除法.没有新建树,

放代码的原意是举例一下sqrt(n)在批处理中的变通.
---------------
昨天晚上在CCTV1看到一个节目,

说一个65岁初中农民用一生的时间来证明歌德巴赫猜想.未果,将愿望寄托与女儿身上..

精神可嘉.......

[ Last edited by qjbm on 2007-1-29 at 07:32 PM ]

Re qzwqzw:

只希望能将现有的算法代码化并能在有效的时间内得出结果

毕竟这里能讨论算法的人很少

能讨论数论的人更是罕见

兄的代码厉害。呵呵，如果有兴趣的话看看这个帖子

用批处理开方倒数的可行性讨论

http://www.cn-dos.net/forum/viewthread.php?tid=23811&fpage=1&highlight=%E5%80%92%E6%95%B0

electronixtar给的链接已阅

感觉批处理化的难度很大

方根倒数通常小于1

这在批处理中处理起来将会很繁琐

除非建立比较完善的浮点数运算机制

-----------------------------------------------------

顶楼代码的溢出上界已得到证明

不用再测试了

set /a result=(x*x) %% %1

这一句决定了在x^2的溢出上界为2^31

所以x的溢出上界为(2^31)^1/2，约为46340

if %tmp2% neq 0 set /a result=(result*%2) %% %1
set x=%result%

这两句决定了x不会大于等于判定数%1，最大值为%1-1

所以%1的溢出上界应该46341

所以可以确定46341之前的所有数确定不会溢出不会误判

46431之后溢出概率级数增大

漏判率也随之级数增大

-----------------------------------------------------

现在我比较倾向于使用新的算法来替代二次检验

搜索中……