Monday, October 06, 2014

Prime counting benchmark

One of those activities certain students may be asked to do is write a prime number counting program.

I've talked about my own simple prime counter often enough but thought I'd give a result from a more advanced algorithm I developed from it, using this applet I built to demonstrate my research. Took the relevant portion from a screenshot I did today for this post:

That is the count of primes up to 1010 and it took a bit over a quarter of a second, which is slow.

But it was my research so I felt it was solid for just coming from some guy who isn't even a mathematician.

If your code isn't close to that speed you're not even trying yet.

The basic prime counter isn't that fast, but you can optimize it easily. I wish I still had the source code. Lost it. I had something I called which is in the applet, but I only have the .class files, and lost the Java files.

I lose TONS of things. Just don't care. Luckily I throw a lot of things up on the web as otherwise it's just gone. One guy had an even more optimized version of my code up on the web, but I don't know if it's still up, where he'd sped it up greatly.

In any event, counting primes is one of those things where lots of people do it, so there's lots of tables around to verify your counts. And it might help to have some perspective on how fast your counter should be.

James Harris
Post a Comment