yoy.be "Why-o-Why"

2011-03-14 00:36 i2957 [permalink]

I once had the idea of building a sieve to find primes, with two arrays of integers: one array with the primes found so far, and one array with a multiple of the corresponding prime which is just above the number currently being investigated. If a multiple would match, it's not a prime, if I wouldn't find a multiple in all previously found primes, I've got a new prime. This way I would not have to multiply or trial-divide anything. All you have to do is start with a first element set to 2, and 'investigate' 3. This is the next prime of course, and 4 hits the next multiple of 2 that's larger than 3 already.

The first go was long (long!) ago back in 16-bits. It found primes up to 65521. But we're having multiple 64-bit monsters purring on our laps nowadays, so I had another go. Turns out the technique spits out primes in sequence faster than I/O can handle, so I had to optimize a bit. Finding all 32-bits primes took a few hours, so I started a 64-bits version somewhere in februari and left it running on a machine I have in the attic that also records television stuff now and then.

I'm not sure if anyone can use *all* of the prime numbers in sequence for something, but there it is. If you want a copy, let me know. I could also make a version of the program that runs on several cores. I could also make a client that gets ranges of numbers to check for primes and post them back. But I'm not planning to do that. I suspect I won't find anything ground-breaking in the primes-world this way.

It does make a nice tool to list sets of primes, and the primes list is great to split any (large) number in its prime factors. Have a look: (but please don't overload my spare machine in the attic!)

**Update:** source code is available here: https://github.com/stijnsanders/primes