Home › Windows Batch Sieve of Eratosthenes

Reply to comment

Windows Batch Sieve of Eratosthenes

Fri, 2007-11-23 00:29 — Joey

A while ago a fellow student of mine held a „lecture“ for pupils on programming where I should help helping the kids. Prime numbers are a nice topic for introductory courses, since they are easy to understand and a simple search for them is written in a few lines of code. I suggested mentioning the Sieve of Eratosthenes as well as giving an implementation of it, since I think the algorithm is pretty easy to understand and nicely fast in generating the first n primes. The programming language we used was Pascal and I was able to come up with a naïve implementation in a manner of minutes. Glancing over the program again I thought it wouldn't be that hard to implement in CMD, so I tried … there was still plenty of time left so I wrote the following perversion of batch language :-)

It's actually very short and I was surprised that it took only that few lines to write. We start by allocating a bunch of n boolean array elements:
set n=%1
for /l %%i in (2,1,%n%) do set l%%i=1
and then we simply iterate over them and delete all those environment variables that resemble multiples of the current number:
:sieve
set /a begin=%1
set /a max=%n% / %1
for /l %%k in (%begin%,1,%max%) do set /a foo=%1 * %%k && set l!foo!=
goto :EOF
and finally we simply output those that are left:
for /l %%i in (2,1,%n%) do if DEFINED l%%i echo %%i
That actually already was most of the code, the rest is merely auxiliary.Now that I look at that code again the sieve loop could as well be
for /l %%k in (%begin%,%1,%max­%) do set l!foo!=
This should work too and we save a variable assignment during the inner loop. But I'm too lazy to do benchmarks now so I just leave it the old way that is tried to work.

There is a practical limit for n, though. The batch runs fine for 100 or even 1000 numbers, but sieving 20000 numbers already takes about a minute on my notebook. And there was a point at which the environment seemed to grow too large to handle in a sensible way.

And no, it does not compute all this in parallel, though I wonder how hard it would be to create batch files that calculate things concurrently in multiple processes; might actually make use of all those multicore systems out there. But I don't have a good idea currently how they should communicate if need arises; files are an option but slow and subject to races … well, I still have a lot of lectures I only attend physically, so my mind may be free to solve these problems :-)

AttachmentSize
sieve.cmd542 bytes
  • 1547 reads

Reply

The content of this field is kept private and will not be shown publicly.