*hypf*

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: and then we simply iterate over them and delete all those environment variables that resemble multiples of the current number: and finally we simply output those that are left: 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 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 :-)

Anhang	Größe
sieve.cmd	542 Bytes