[permalink]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
