标题: [讨论]寻找大素数-32位正整数的素性判定 [打印本页]
作者: qzwqzw 时间: 2007-1-29 00:11 标题: [讨论]寻找大素数-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 ]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
作者: redtek 时间: 2007-1-29 02:14
顶～～欣赏～～～
作者: pengfei 时间: 2007-1-29 02:31
qzwqzw兄的代码精彩~~~ 支持!
由于批处理中set /a进行算术运算时可以存储的最大值为长整型(32 位), 正数为2147483647, 负数为-2147483648. 再多加或减1时都会溢出.
作者: pengfei 时间: 2007-1-29 02:57
批处理进行大数判定时效率还是很慢, 可以单独判定一个数是否素数, 这样能更好地讨论一些算法的实现.
作者: qzwqzw 时间: 2007-1-29 03:39
实际上顶楼的代码实现的就是单个大素数的判定
代码中的循环只是用来判断其算法的有效性
而代码的效率可以通过从语法上的改善来提高
--------------------------------------------------
关于整型溢出的上下界是受cmd本身的限制
不仅仅是set/a而已
要想解决数据溢出的问题
一是寻找不使用二次检验的确定性判定算法
二是构建cmd处理64位整数的能力
这可能是我们讨论的主要方向
---------------------------------------------------
也许用64位Windows的CMD也可以解决
不知谁有测试环境可以测试一下
作者: pengfei 时间: 2007-1-29 04:37
建议兄做成一个让用户自己输入一个数, 再判断该数是否为素数.
此代码效率很差, 只是演示.
@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代替.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
[ Last edited by pengfei on 2007-1-29 at 04:45 AM ]
作者: qzwqzw 时间: 2007-1-29 05:35
感觉用户输入没有什么大用
较小的数都已测试过
较大的数是素数的概率比较低
测试的效率很低
-------------------------------------
不过也好
就加上一个输入判断
如果输入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
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
作者: qjbm 时间: 2007-1-30 04:55
我的建议是先采集判断方法,然后再代码化.
对一个素数的判定,我的方法是:
--------------
条件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万 时效率尚可,时间为: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
开始: 16:10:48.95
结束: 16:14:01.56
[ Last edited by qjbm on 2007-1-29 at 04:17 PM ]
作者: qzwqzw 时间: 2007-1-30 05:51
编辑中有删除本帖的功能，可以试试
判定算法在顶楼给的链接里有讨论
你所给出的算法中对10的取模倒是很有创意
但给数时通常步进值取2
所以判断时可以不考虑0/2/4/6/8的尾数
而5是素数表中第三个素数
很快就会被试除法用来做判定
因此节约的性能可能很有限
作者: qzwqzw 时间: 2007-1-30 06:07
另外请注意
这里主要探讨单个32位正整数的素性判定
素数表的方法通常用于判定一个素数群
而且理论上说
如果要判定一个最大的32位正整数是否正整数
你的算法（实际上以前也讨论过这些算法）要构建的素数表就太大了
大约需要四千多个素数才能通过试除法判定
而且你的生成素数表的算法并没有优化
即没有到sqrt(n)就停止生成素数
素数表会大很多
系统环境空间明显是不够用的
[ Last edited by qzwqzw on 2007-1-29 at 05:09 PM ]
作者: qjbm 时间: 2007-1-30 06:54
在8楼的代码中,由于批处理无法进行sqrt(n)计算
所以使用了:
SET /A K=%%j*%%j
IF !K! GTR %1 GOTO :EOF
进行控制,相当于到sqrt(n)就停止.IF !K! GTR %1 GOTO :EOF
不过此种方法还是试除法.没有质的突破.
关于:
米勒-拉宾法加二次检测后所有的最小可判定底数都不大于n^(1/6)仍然只是一个
猜想,无法证明.我也曾利用试除法,对50万以内素数进行各种处理以寻找规律,
但都是在一定范围内有效....不能完全公式化..唔...可以公式化就留名青史了...:)
可以以此贴收集众家之长,说不定自然数素性判定法公式就在本贴产生.
[ Last edited by qjbm on 2007-1-29 at 06:11 PM ]
作者: qzwqzw 时间: 2007-1-30 07:26
关于8楼代码也许我理解的有误
IF !K! GTR %1 GOTO :EOF
感觉它只是控制试除的上界
而非生成素数的上界
比如判断一个整数7是否素数
素数表只需要生成到3就可以了
而你的素数表会生成到5
虽然它只会试除到3
所以在显示完是否素数后
应该再加一个判断
看是否需要将这个素数追加到到素数表
这个优化在顶楼提到了链接里已经有间接的实现了
------------------------------------------------
我是没奢望能讨论出新的判定公式了
只希望能将现有的算法代码化并能在有效的时间内得出结果
毕竟这里能讨论算法的人很少
能讨论数论的人更是罕见
作者: qjbm 时间: 2007-1-30 08:27
你的理解没有太大误差,
在被判断的自然数为质数时,被枚举素数表上限确实多一个.但不对其进行试除.
但是在被判断的自然数为合数时,是不到上限即可断定,
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 ]
作者: electronixtar 时间: 2007-1-30 09:18
Re qzwqzw:
| Quote: | |
|
兄的代码厉害。呵呵，如果有兴趣的话看看这个帖子
[讨论]用批处理开方倒数的可行性讨论
http://www.cn-dos.net/forum/view ... =%E5%80%92%E6%95%B0
作者: qzwqzw 时间: 2007-1-30 11:46
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之后溢出概率级数增大
漏判率也随之级数增大
-----------------------------------------------------
现在我比较倾向于使用新的算法来替代二次检验
搜索中……
作者: tao0610 时间: 2007-1-30 11:52
汗......费尔马小定理可判定上界猜想,神奇!