c - 针对内存优化的初筛

Question

我正在寻找一种在内存消耗方面高效的素筛实现。

当然，素数测试本身应该以恒定的和最小操作数执行。

我已经实现了一个筛子，该筛子仅指示与 6 的倍数相邻的数字的素数。

对于任何其他数字，要么是 2 或 3(因此是质数)，要么是 2 或 3 的倍数(因此是非质数)。

所以这就是我想出的，我一直想知道在这些要求下是否有更好的东西:

接口(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

实现:

#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);
}

Answer 1

您已经正确地推断出您可以利用只有两个数与 6 互质的事实，即 1 和 5(又名 +1 和 -1)。使用这个事实并将筛子存储为位而不是字节，您可以将内存需求减少 24 倍。

为了节省一点内存，你可以进入下一层，注意只有 8 个数(模 30)与 30 互质。它们是 1, 7, 11, 13, 17, 19, 23、29。使用该事实并存储为位，内存减少了 30 倍。

实现注意事项:筛子中的每个字节代表与 30 的某个倍数互质的 8 个数字。例如，sieve[3] 中包含的位代表数字 91、97 , 101, ...