Sieve of Eratosthenes - optimization - remove even numbers

[serolf]

I'm working on this problem and I could use any help I can get.

I want to optimize an already parallel Sieve of Eratosthenes program
by not allocating memory for even numbers, since they're never primes
(besides 2). This Sieve program only counts the number of primes from
2...n, it doesn't actually display them, just counts.
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

I've got the code here. It should compile though you'll need a utility
class "mympi.h and mympi.c"
http://pastebin.com/m3bcc6502
http://www.soe.ucsc.edu/classes/cmpe113/Spring07/source/

There's a few printf statements to help me out. I tried making changes
to the size (dividing by 2) and then modifying the main do-while loop
with no success. I think the key might be when it's incrementing i by
prime. But it doesn't seem to work.

Thanks in advance.

[Georg Bisseling]

Post by serolf
I'm working on this problem and I could use any help I can get.
I want to optimize an already parallel Sieve of Eratosthenes program
by not allocating memory for even numbers, since they're never primes
(besides 2). This Sieve program only counts the number of primes from
2...n, it doesn't actually display them, just counts.
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
I've got the code here. It should compile though you'll need a utility
class "mympi.h and mympi.c"
http://pastebin.com/m3bcc6502
http://www.soe.ucsc.edu/classes/cmpe113/Spring07/source/
There's a few printf statements to help me out. I tried making changes
to the size (dividing by 2) and then modifying the main do-while loop
with no success. I think the key might be when it's incrementing i by
prime. But it doesn't seem to work.
Thanks in advance.

I think the key to the problem is to separate the algorithm from the
data structure implementation to store the flags. Nowadays you would
not call that structured programming but object oriented. Choose your
flavor. I will stick to plain C for the moment.

Just introduce a data structure

typedef struct storage_tag {
/* left to the reader */
} storage;

and some functions

storage *storage_create(long upperLimit);
void storage_delete(storage *s);
bool storage_query(storage *s, long index) {
if (2 == index) return false; /* two is prime */
if (0 == index & 1) return true; /* even numbers are marked */
/* ... */
}
void storage_set(storage *s, long index, bool value);

and write your algorithm in terms of the storage interface.

After improving your memory requirements by a factor of
two you can tackle the problem of replacing the char in the
storage with a single bit to gain another factor of eight
- without having to touch the algorithm.

Happy programming!