批量质数

Question

我一直在做一个使用批处理文件的小项目，我遇到了一个问题。据我所知，没有办法检查某个变量是否是质数，如果我错了，请谁告诉我怎么做，否则，有没有人能想到一个我可以使用的变通办法(比如检查一个数字是否等于一个txt文件的质数列表上的一个数字)。谢谢^^ (另外值得一提的是，我对批处理文件不是很了解，所以请原谅我可能会出现的任何愚蠢的行为。)

Answer 1

如果您有一个包含质数的文本文件，每行1个(显然达到了某些限制)，那么解决方案很简单--只需使用FINDSTR即可。

假设您有一个包含数字的数字变量，那么

>nul findstr /x %NUMBER% "primes.txt" && (
    REM prime actions go here
    echo %NUMBER% is prime
) || (
    REM not prime actions go here
    echo %NUMBER% is NOT prime
)

更新

这是一个本地批处理脚本，可以测试batch (有符号32位整数)支持的任何有效整数，以查看它是否为质数。性能比我想象的要好得多。

::testPrime  Number
::
::  Computes whether Number is a prime or not.
::  The result is printed to stdout.
::
::  ERRORLEVEL is also set to indicate the result:
::    0 = Prime
::    1 = Not Prime
::    2 = Error
::
::  Number = Any valid integral expression supported by SET /A
::
@echo off
if "%~1"=="test" (
  setlocal enableDelayedExpansion
  for /l %%N in (3 2 0x7fffffff) do (
    set /a "test1=num %% %%N, test2=%%N*%%N"
    if !test1! equ 0 exit 1
    if !test2! gtr !num! exit 0
  )
)

setlocal disableDelayedExpansion
2>nul set /a "num=%~1" || (
  >&2 echo invalid number: %1
  exit /b 2
)
if %num% leq 1 (
  echo %num% is NOT prime
  exit /b 1
)
if %num% leq 3 (
  echo %num% is prime
  exit /b 0
)
2>nul set /a "1/(num %% 2)" || (
  echo %num% is NOT prime
  exit /b 1
)
(
  cmd /c "%~f0" test
) && (
  echo %num% is prime
  exit /b 0
) || (
  echo %num% is NOT prime
  exit /b 1
)
exit /b

测试实际上被分成两部分，第二部分实际上是在一个新的CMD实例中运行。第二部分实际上出现在脚本的顶部。这样做是出于性能原因。这是我可以立即跳出FOR /L循环而不终止批处理脚本的唯一方法。

您可以很容易地将代码与脚本集成在一起。例如：

@echo off
::----------------------------------------------------
:: This 2nd part of :testPrime must be at top of script
::
if "%~1"=="test" (
  setlocal enableDelayedExpansion
  for /l %%N in (3 2 0x7fffffff) do (
    set /a "test1=num %% %%N, test2=%%N*%%N"
    if !test1! equ 0 exit 1
    if !test2! gtr !num! exit 0
  )
)
:: End of 2nd part of :testPrime
::-----------------------------------------------------
:: Your code goes here
:: I'll just call the test with some representative values
::
setlocal disableDelayedExpansion
for %%N in (
  1 2 3 4 100001 100003 5000009 5000011 0x7fffffff-2 0x7fffffff
) do  >nul call :testPrime %%N && (
  rem prime number actions go here
  echo %%N is prime!
) || (
  rem non-prime number actions go here
  echo                           Not prime (%%N^)
)
exit /b

::----------------------------------------------------
:: Here is the 1st part of :testPrime
::
:testPrime
2>nul set /a "num=%~1" || (
  >&2 echo invalid number: %1
  exit /b 2
)
if %num% leq 1 (
  echo %num% is NOT prime
  exit /b 1
)
if %num% leq 3 (
  echo %num% is prime
  exit /b 0
)
2>nul set /a "1/(num %% 2)" || (
  echo %num% is NOT prime
  exit /b 1
)
(
  cmd /c "%~f0" test
) && (
  echo %num% is prime
  exit /b 0
) || (
  echo %num% is NOT prime
  exit /b 1
)
exit /b

上面的输出如下所示：

                          Not prime (1)
2 is prime!
3 is prime!
                          Not prime (4)
                          Not prime (100001)
100003 is prime!
                          Not prime (5000009)
5000011 is prime!
                          Not prime (0x7fffffff-2)
0x7fffffff is prime!

最后，对于讨厌的人，我写了一个变体，列出下一个质数>=或<=给定的数字。

::nextPrime [/less]  Num
::
::  List the minimum prime number >= Num
::
::  The /L option lists the maximum prime number <= Num
::
::  The ERRORLEVEL is set to the found prime number
::
::  Num = Any valid integral expression supported by SET /A
::
@echo off
setlocal enableDelayedExpansion
if "%~1"=="test" (
  for /l %%N in (3 2 0x7fffffff) do (
    set /a "test1=%2 %% %%N, test2=%%N*%%N"
    if !test1! equ 0 exit 1
    if !test2! gtr %2 exit 0
  )
)
if "%~1"=="prev" (
  if !num! lss 2 exit 0
  set /a "test=num%%2"
  if !test! equ 0 set /a num-=1
  for /l %%N in (!num! -2 2) do cmd /c "%~f0" test %%N && exit %%N
  exit 0
)
if "%~1"=="next" (
  if !num! lss 2 exit 2
  set /a "test=!num!%%2"
  if !test! equ 0 set /a num+=1
  for /l %%N in (!num! 2 0x7fffffff) do cmd /c "%~f0" test %%N && exit %%N
  exit 0
)
set "cmd=next"
if /i "%~1" equ "/L" (
  set "cmd=prev"
  shift /1
)
2>nul set /a "num=%~1" || exit /b 0
cmd /c "%~f0" %cmd% || echo !errorlevel!

下面是输出的用法演示：

D:\test>nextPrime 10000000
10000019

D:\test>nextPrime /l 10000000
9999991

Answer 2

对我来说，所有这些脚本看起来都太大了(而且没有必要)。

一种更简单的方法是使用...我相信我正在寻找的术语要么是模数，要么是模数表达式(我认为模数是复数或模数)。

@echo off & setlocal enabledelayedexpansion

:a
cls
set /p num=Type a number to be checked: 
cls
set num2=%num%-1

if %num% leq 2 goto yes
for /l %%i in (2,1,%num2%) do (
    set rem=%num% %% %%i
    if %rem% neq 0 goto no
)

:yes
echo %num% is a prime number.
pause
goto a

:no
echo %num% is not a prime number.
pause
goto a

基本上，它获取一个用户定义的变量，并在除以一个数字时检查余数(rem)是否为0。

这种方式有点慢，但代码最短。您可以通过在for循环之前放置另一条if语句来检查该数字除以二时是否有余数，从而使其更短。

希望能有所帮助。

Answer 3

另一个主要列表器，这个不使用文件，如果你有耐心的话可以达到6400万。在环境变量中保留主除数列表。如果我有一个批量整数平方根例程，我可以让它更快。

@echo off
::batch prime list up to 64M by Antoni Gual
:: does not use files!!

setlocal enabledelayedexpansion
set bitmap=
set n=Y
set /a test=3,npri=3
echo 1th prime is 2 & echo 2th prime is 3 

:nextpri
set /a test+=2,index=0,div=3
if %test% LSS 8000 set bitmap=%bitmap%%n%
if %test% gtr 64000000 exit /b 

:nextest
if "!bitmap:~%index%,1!"=="N" goto nextdiv
set /a resi=!test!%%!div!
if %resi% equ 0 set n=N& goto nextpri

:nextdiv
set /a index+=1, div+=2
set /a div2=div*div 
if %div2% gtr %test% (
set n=Y
echo %npri%th prime is %test% 
set /a npri+=1 
goto nextpri)
goto nextest