用位来代替bool：减小内存使用，提高运行速度

素数槽问题

Description

       处于相邻的两个素数p和p + n之间的n - 1个连续的合数所组成的序列我们将其称为长度为n的素数槽。例如，‹24, 25, 26, 27, 28›是处于素数23和素数29之间的一个长度为6的素数槽。

       你的任务就是写一个程序来计算包含整数k的素数槽的长度。如果k本身就是素数，那么认为包含k的素数槽的长度为0。

Input

第一行是一个数字n，表示需要测试的数据的个数。后面有n行，每行是一个正整数k， k大于1并且小于或等于的第十万个素数（也就是1299709）。

Output

对于输入部分输入的每一个k，都对应输出一个非负整数，表示包含k的素数槽的长度，每个非负整数占一行。

分析：

用筛法标记素数，首先要定义规模相当的数组，如果采用int、char类型或者C++中的bool，会造成“浪费”，因为标记一个数是否为素数实际上只需要一位(bit)。

另外，虽然看上去多了索引位、置位的操作，运行时间却减少了。

索引位、置位利用宏实现。

# include <stdio.h>
# define MAX 1299710
# define INDEX(i) ((i)>>(3))
# define OFFSET(i) ((i)%(8))
# define get_bit(i) ((mark[INDEX(i)]>>OFFSET(i)) & (0x1))
# define set_bit(i) (mark[INDEX(i)] |= (char)(0x1<<OFFSET(i)))

// 或者char mark[(MAX>>3)+1]; 此时必须加括号!
char mark[INDEX(MAX)+1];      

int main()
{
    int i, n, k, j, len;

    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);

    for (i = 2; i < MAX; ++i)
    {
        if (get_bit(i)) continue;
        for (j = 2*i; j < MAX; j += i)
            set_bit(j);
    }

    scanf("%d", &n);
    for (i = 0; i < n; ++i)
    {
        scanf("%d", &k);
        len = 0;
        j = k;
        while (get_bit(k)) --k;
        while (get_bit(j)) ++j;
        len = j - k;
        printf("%d\n", len);
    }

    return 0;
}