Board logo

标题: [讨论]寻找大素数-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 ]
作者: 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代替.

[ 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

作者: 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万 时效率尚可,时间为:
开始: 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)就停止.

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

关于:
米勒-拉宾法加二次检测后所有的最小可判定底数都不大于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
汗......费尔马小定理可判定上界猜想,神奇!