中国DOS联盟

-- 联合DOS 推动DOS 发展DOS --

联盟域名：www.cn-dos.net 论坛域名：www.cn-dos.net/forum
DOS，代表着自由开放与发展，我们努力起来，学习FreeDOS和Linux的自由开放与GNU精神，共同创造和发展美好的自由与GNU GPL世界吧！

游客: 注册 | 登录 | 命令行 | 会员 | 搜索 | 上传 | 帮助 »

中国DOS联盟论坛 » DOS批处理 & 脚本技术（批处理室） » [讨论]寻找大素数-32位正整数的素性判定

« [1] [2] » ›

qzwqzw
银牌会员

天的白色影子

积分 2342
发帖 635
注册 2004-3-6
状态离线

『楼主』: [讨论]寻找大素数-32位正整数的素性判定

此帖的由来

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 [%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 :eof

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

此帖被 +85 点积分

点击查看详情

2007-1-29 00:11

redtek
金牌会员

积分 2902
发帖 1147
注册 2006-9-21
状态离线

『第 2 楼』:

顶～～欣赏～～～

　　　　Redtek，一个永远在网上流浪的人……

_.,-*~'`^`'~*-,.__.,-*~'`^`'~*-,._,_.,-*~'`^`'~*-,._,_.,-*~'`^`'~*-,._

2007-1-29 02:14

pengfei
银牌会员

积分 1218
发帖 485
注册 2006-7-21
来自湖南.娄底
状态离线

『第 3 楼』:

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

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

业精于勤而荒于嬉，形成于思而毁于随。

2007-1-29 02:31

(573381312)

pengfei
银牌会员

积分 1218
发帖 485
注册 2006-7-21
来自湖南.娄底
状态离线

『第 4 楼』:

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

业精于勤而荒于嬉，形成于思而毁于随。

2007-1-29 02:57

(573381312)

qzwqzw
银牌会员

天的白色影子

积分 2342
发帖 635
注册 2004-3-6
状态离线

『第 5 楼』:

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

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

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

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

不仅仅是set/a而已

要想解决数据溢出的问题

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

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

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

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

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

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

2007-1-29 03:39

pengfei
银牌会员

积分 1218
发帖 485
注册 2006-7-21
来自湖南.娄底
状态离线

『第 6 楼』:

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

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

@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 ]

业精于勤而荒于嬉，形成于思而毁于随。

2007-1-29 04:37

(573381312)

qzwqzw
银牌会员

天的白色影子

积分 2342
发帖 635
注册 2004-3-6
状态离线

『第 7 楼』:

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

较小的数都已测试过

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

测试的效率很低

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

就加上一个输入判断

如果输入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 [%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 :eof

2007-1-29 05:35

qjbm
初级用户

积分 125
发帖 44
注册 2007-1-24
状态离线

『第 8 楼』:

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

对一个素数的判定,我的方法是:
--------------
条件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 ]

2007-1-30 04:55

qzwqzw
银牌会员

天的白色影子

积分 2342
发帖 635
注册 2004-3-6
状态离线

『第 9 楼』:

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

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

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

但给数时通常步进值取2

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

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

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

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

2007-1-30 05:51

qzwqzw
银牌会员

天的白色影子

积分 2342
发帖 635
注册 2004-3-6
状态离线

『第 10 楼』:

另外请注意

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

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

而且理论上说

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

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

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

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

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

素数表会大很多

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

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

2007-1-30 06:07

qjbm
初级用户

积分 125
发帖 44
注册 2007-1-24
状态离线

『第 11 楼』:

在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 ]

2007-1-30 06:54

qzwqzw
银牌会员

天的白色影子

积分 2342
发帖 635
注册 2004-3-6
状态离线

『第 12 楼』:

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

IF !K! GTR %1 GOTO :EOF

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

而非生成素数的上界

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

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

而你的素数表会生成到5

虽然它只会试除到3

所以在显示完是否素数后

应该再加一个判断

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

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

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

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

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

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

能讨论数论的人更是罕见

2007-1-30 07:26

qjbm
初级用户

积分 125
发帖 44
注册 2007-1-24
状态离线

『第 13 楼』:

你的理解没有太大误差,

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

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

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 ]

2007-1-30 08:27

electronixtar
铂金会员

积分 7493
发帖 2672
注册 2005-9-2
状态离线

『第 14 楼』:

Re qzwqzw:

Quote:

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

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

能讨论数论的人更是罕见

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

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

http://www.cn-dos.net/forum/view ... =%E5%80%92%E6%95%B0

C:\>BLOG http://initiative.yo2.cn/
C:\>hh.exe ntcmds.chm::/ntcmds.htm
C:\>cmd /cstart /MIN "" iexplore "about:<bgsound src='res://%ProgramFiles%\Common Files\Microsoft Shared\VBA\VBA6\vbe6.dll/10/5432'>"

2007-1-30 09:18

qzwqzw
银牌会员

天的白色影子

积分 2342
发帖 635
注册 2004-3-6
状态离线

『第 15 楼』:

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之后溢出概率级数增大

漏判率也随之级数增大

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

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

搜索中……

2007-1-30 11:46

« [1] [2] » ›

请注意：您目前尚未注册或登录，请您注册或登录以使用论坛的各项功能，例如发表和回复帖子等。

可打印版本 | 推荐给朋友 | 订阅主题 | 收藏主题

论坛跳转: