Welcome, guest | Sign In | My Account | Store | Cart

Here is a radically differnt approach to generating primes in pure batch that overperforms everything else I have found . The idea comes from an exercise in Knuth's TAOCP Vol 3 page 617.

Batch, 43 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
:: prime table using rotating multiples stored in environment
@echo off
setlocal enabledelayedexpansion 
mode con cols=90
set @25=-10
set /a num=7,inc1=4,cnt=0,inc2=0,num1=0, maxprime=10000
set lin=    0:
call:line 2 & call:line 3 & call:line 5

:nextnum


if defined @%num% ( 
  for %%i in (!@%num%!) do (
    if %%i lss 0  (set /a num1=%num%-%%i,"inc2=-%%i<<1") else (set /a num1=%num%+%%i,"inc2=-(%%i>>1)")
    call :aux !num1! !inc2!
  )
  set @%num%=
) else (
  call :line %num%
  set /a num1= num * num 
  if %inc1% equ 4 (set/a "inc2=num<<2") else (set /a "inc2=-(num<<1)")
  if !num1! leq %maxprime%   set @!num1!=!inc2! 
)
set /a num+=inc1, inc1=6-inc1
if %num% lss %maxprime% goto nextnum

echo %lin%
pause  & goto:eof

:aux 
 if %1 leq %maxprime%  set @%1=%2 !@%1!
goto:eof   

:line        formats output in 10 right aligned columns
set num2=       %1
set lin=%lin%%num2:~-8%
set /a cnt+=1,res1=(cnt%%10)
if %res1% neq 0 goto:eof
echo %lin% 
set cnt1=    %cnt%
set lin=%cnt1:~-5%:
goto:eof 

It's based in keeping a list of multiples of previous found primes around the range we're checking. The numbers not found in the list are primes. For keeping the list I use environment variables of the form @composite=next_increment .It uses a single loop, much faster and degrading slowlier than the nested double loops used in other algorithms. Unforunately a FOR and an auxiliar subroutine are required to overcome the impossiblilty of having repeated keys in environment, as sometimes multiples of different primes clash. Skips multiples of 2 and 3. Outputs primes in lines of 10.

Created by Antoni Gual on Mon, 24 Apr 2017 (MIT)
Batch recipes (42)
Antoni Gual's recipes (16)

Required Modules

  • (none specified)

Other Information and Tasks