Prime Sieve is optimized for memory
I'm looking for a simple sieve implementation that is efficient in terms of memory consumption.
Of course, the primality test itself should be performed with a constant and minimal number of operations.
I have implemented a sieve that indicates simplicity only for numbers that are adjacent to multiples of 6.
For any other number, either it is 2 or 3 (therefore prime) or a multiple of 2 or 3 (therefore odd).
So, this is what I came up with and I was wondering if there is something better about these requirements:
Interface:
#include <limits.h>
// Defined by the user (must be less than 'UINT_MAX')
#define RANGE 4000000000
// The actual length required for the prime-sieve array
#define ARR_LEN (((RANGE-1)/(3*CHAR_BIT)+1))
// Assumes that all entries in 'sieve' are initialized to zero
void Init(char sieve[ARR_LEN]);
// Assumes that 'Init(sieve)' has been called and that '1 < n < RANGE'
int IsPrime(char sieve[ARR_LEN],unsigned int n);
#if RANGE >= UINT_MAX
#error RANGE exceeds the limit
#endif
Implementation:
#include <math.h>
#define GET_BIT(sieve,n) ((sieve[(n)/(3*CHAR_BIT)]>>((n)%(3*CHAR_BIT)/3))&1)
#define SET_BIT(sieve,n) sieve[(n)/(3*CHAR_BIT)] |= 1<<((n)%(3*CHAR_BIT)/3)
static void InitOne(char sieve[ARR_LEN],int d)
{
unsigned int i,j;
unsigned int root = (unsigned int)sqrt((double)RANGE);
for (i=6+d; i<=root; i+=6)
{
if (GET_BIT(sieve,i) == 0)
{
for (j=6*i; j<RANGE; j+=6*i)
{
SET_BIT(sieve,j-i);
SET_BIT(sieve,j+i);
}
}
}
}
void Init(char sieve[ARR_LEN])
{
InitOne(sieve,-1);
InitOne(sieve,+1);
}
int IsPrime(char sieve[ARR_LEN],unsigned int n)
{
return n == 2 || n == 3 || (n%2 != 0 && n%3 != 0 && GET_BIT(sieve,n) == 0);
}
source to share
You have correctly identified that you can use the fact that there are only two numbers that are relatively prime with 6, that is, 1 and 5 (aka +1 and -1). By using this fact, and by storing the sieve as bits instead of bytes, you reduce your memory requirement by a factor of 24.
To save a little more memory, you can go to the next level and note that there are only 8 numbers (mod 30), which are a relatively prime number 30. They are 1, 7, 11, 13, 17, 19, 23, 29. Using this fact and storing it as bits, the memory is reduced by a factor of 30.
Implementation note: Each byte in a sieve represents 8 coprime numbers with multiple multiples of 30. For example, the bits contained in sieve[3]
represent numbers91, 97, 101, ...
source to share