China DOS Union

Origin of this post

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

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

The following code completely copies the judgment algorithm in the following link - Miller-Rabin test + quadratic test

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

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

Unfortunately, the quadratic test will cause data overflow in large prime number judgment

The test results start from 46400 and a large number of missed detections due to data overflow occur

No missed detection in the test within 1000

No test from 1000 to 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  %=This code judgment causes data overflow in large primes=%

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 ]

Top~~Appreciate~~~

Brother qzwqzw's code is wonderful~~~ Support!

When performing arithmetic operations with set /a in batch processing, the maximum value that can be stored is a 32-bit signed integer, with the positive number being 2147483647 and the negative number being -2147483648. Adding or subtracting 1 more will cause an overflow.

When performing large number judgment in batch processing, the efficiency is still very slow. We can individually judge whether a number is a prime number, which can better discuss the implementation of some algorithms.

Actually, the code in the top post is actually implementing the determination of a single large prime number.

The loop in the code is just used to judge the effectiveness of its algorithm.

And the efficiency of the code can be improved through grammatical improvements.

--------------------------------------------------
The upper and lower bounds of integer overflow are limited by the cmd itself.

It's not just set/a.

To solve the problem of data overflow.

One is to find a deterministic determination algorithm that does not use quadratic testing.

The second is to build the ability of cmd to handle 64-bit integers.

This may be the main direction of our discussion.

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

Maybe the CMD of 64-bit Windows can also solve it.

I don't know who has a test environment to test it.

Suggest the brother to make a program where the user enters a number and then judges whether the number is a prime number.

This code has very poor efficiency, just for demonstration.

@echo off

setlocal enabledelayedexpansion

set /p num=Please enter a number:

echo Judging, please wait...

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% is a prime number.) else (echo %num% is not a prime number.)

echo Start time=%t%

echo End time=%time%

pause

Because the square root of a number cannot be calculated in batch processing, here it is replaced by dividing by 2.

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

It feels that the user input is not very useful.

Smaller numbers have all been tested.

The probability that larger numbers are prime is relatively low.

The efficiency of testing is very low.

-------------------------------------
But it's also okay.

Just add an input judgment.

If input i, use the built-in test set to determine prime numbers.

Otherwise, perform the judgment of a single prime number.

@echo off

setlocal EnableDelayedExpansion



:loop_test

set testnum=

set /p testnum=Please enter an integer (press i to use the built-in test set, press Enter directly to exit): 

if "%testnum%"=="" goto :eof

if /i not "%testnum%"=="i" (

    call :JudgePrime %testnum%

    if errorlevel 2 (echo Invalid input: %testnum%

    ) else if errorlevel 1 (echo %testnum% is a prime number

    ) else (echo %testnum% is a composite number)

    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  %=This code judgment causes data overflow when dealing with large primes%

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

My suggestion is to first collect the judgment method and then code it.

For the judgment of a prime number, my method is:
--------------
Condition 1.
Any natural number greater than 2, if %%10 NEQ 1\3\7\9, it is a composite number.

Condition 2.
For those not meeting condition 1, if it can be divided evenly by any prime number less than its square root, it is a composite number.

Those not meeting conditions 1 and 2 are prime numbers.
-------------------
The biggest shortcoming of this method is that it is necessary to calculate "all prime numbers less than the square root of the number to be tested".

However, this method can keep a list of prime numbers from small to large, which can significantly improve efficiency in multiple detections.

Especially when "the subsequent detection is within the range of the previous detection", the efficiency is higher.

Regarding the problem that the square root cannot be calculated in batch processing, it can be circumvented. In the enumeration process, use the IF statement for control.

For example: In the :MAIN segment in my following code, IF...ELSE...

@ECHO %DBG% OFF

SETLOCAL ENABLEDELAYEDEXPANSION



SET /P X=Please enter a natural number greater than 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

This code, with a 2.7/512 configuration, has acceptable efficiency when X=100,000. The time is:
Start: 16:10:48.95
End: 16:14:01.56

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

There is a function to delete this post in the editor, you can try. The determination algorithm has discussions in the link given at the top floor. The modulo operation of 10 in the algorithm you provided is quite creative. But when giving numbers, usually the step value is taken as 2. So when judging, you can not consider the tail numbers of 0/2/4/6/8. And 5 is the third prime number in the prime number table, which will soon be used by the trial division method for judgment. Therefore, the performance saved may be very limited.

Also please note

Here mainly discuss the primality test of a single 32-bit positive integer

The method of prime table is usually used to determine a group of primes

And theoretically speaking

If you want to determine whether the largest 32-bit positive integer is a positive integer

Your algorithm (in fact, these algorithms have been discussed before) needs to build a prime table that is too large

It is approximately necessary to have more than four thousand primes to pass the trial division test

And your algorithm for generating the prime table is not optimized

That is, it does not stop generating primes until sqrt(n)

The prime table will be much larger

The system environment space is obviously not enough

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

In the code on the 8th floor, since batch processing cannot perform sqrt(n) calculations, the following was used:

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

IF !K! GTR %1 GOTO :EOF 

to control, which is equivalent to stopping when reaching sqrt(n). However, this method is still trial division, and there is no breakthrough in nature. Regarding the fact that all the smallest determinable bases after the Miller-Rabin method plus quadratic detection are all not greater than n^(1/6) is still just a conjecture and cannot be proved. I have also used trial division to process prime numbers within 500,000 in various ways to find patterns, but they are only effective within a certain range.... It cannot be completely formulaic.. Well... If it could be formulaic, it would be famous... :) This post can collect the strengths of everyone, and maybe the formula for the primality determination method of natural numbers will be generated in this post.

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

There might be a misunderstanding about the code on floor 8.

IF !K! GTR %1 GOTO :EOF

It seems it just controls the upper bound of trial division rather than the upper bound of generating prime numbers. For example, to determine whether the integer 7 is a prime number, the prime number table only needs to be generated up to 3. But your prime number table will generate up to 5. Although it will only perform trial division up to 3. So after displaying whether it is a prime number, there should be an additional judgment to see if this prime number needs to be appended to the prime number table. This optimization was mentioned in the top floor, and there is an indirect implementation in the linked content.

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

I didn't expect to discuss a new judgment formula. I just hope to code the existing algorithm and get the result within an effective time. After all, there are few people who can discuss algorithms here, and even fewer who can discuss number theory.

Your understanding is not too inaccurate.

When the natural number to be judged is a prime number, the upper limit of the enumerated prime number table is indeed one more. But it is not divided by trial.

But when the natural number to be judged is a composite number, it can be determined before reaching the upper limit.

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

Enumerate until it is divisible to determine.

I suggest not discussing the code on floor 8 anymore, because it's just a trial division. There is no new tree built.

The original intention of putting the code is to give an example of the workaround of sqrt(n) in batch processing.
---------------
I saw a program on CCTV1 last night,

It said that a 65-year-old junior high school farmer spent his whole life proving Goldbach's conjecture. He failed and entrusted his wish to his daughter..

Admirable spirit.......

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

Re qzwqzw:

Just hope to code the existing algorithm and get results within an effective time

After all, there are few people who can discuss algorithms here

People who can discuss number theory are even rarer

Brother's code is amazing. Hehe, if you are interested, take a look at this thread

Feasibility Discussion of Square Root Reciprocal with Batch Processing

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

The link given by electronixtar has been read.

It feels that the difficulty of batch processing is quite great.

The reciprocal of the square root is usually less than 1.

This will be very tedious to handle in batch processing.

Unless a relatively perfect floating-point operation mechanism is established.

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

The upper bound of overflow of the code in the top floor has been proved.

No need to test anymore.

The sentence "set /a result=(x*x) %% %1" determines that the upper bound of overflow of x^2 is 2^31.

So the upper bound of overflow of x is (2^31)^1/2, approximately 46340.

The two sentences "if %tmp2% neq 0 set /a result=(result*%2) %% %1" and "set x=%result%" determine that x will not be greater than or equal to the judgment number %1, and the maximum value is %1-1.

So the upper bound of overflow of %1 should be 46341.

So it can be determined that all numbers before 46341 will not overflow and will not be misjudged.

The probability level of overflow increases after 46431.

The false judgment rate also increases at the same level.

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

Now I am more inclined to use a new algorithm to replace the quadratic test.

Searching...