一个线性筛的算法

我是算法

/*8888888888888888888*/
#include <stdio.h>
#include <math.h>
#include <time.h>
#define C17 510510
#define SIZE 255255
char BaseCache[SIZE],WorkCache[SIZE];
int PRIMES [43000];
int LOWSQRT, HIGHSQRT; //起始位置和结束位置的平方根
void initCache(void)
{
int p,i;
for ( i = 0; i < SIZE ; i++ )
BaseCache[i] = 1;
for ( p = 3; p <= 17; p+=2 )
{
if ( p == 9 || p == 15 )
continue;
for ( i = p >> 1; i < SIZE; i+=p )
BaseCache[i] = 0;
}
}
void firstSieve(void)
{
int p,i,j,delta = 36,cigema = 180;
for ( i = 0; i < SIZE; i++ )
WorkCache[i] = BaseCache[i];
LOWSQRT = (int)sqrt(C17-1);
for ( p = 19; p <= LOWSQRT; p+=2 )
{
if (WorkCache[p >> 1])
for ( j = cigema; j < SIZE; j+=p )
WorkCache[j] = 0;
delta += 4;
cigema += delta;
}
WorkCache[1] = 1;
WorkCache[2] = 1;
WorkCache[3] = 1;
WorkCache[5] = 1;
WorkCache[6] = 1;
WorkCache[8] = 1;
j = 1; PRIMES[j] = 2;
for (i = 1; i < SIZE; i++)
if (WorkCache[i])
PRIMES[++j] = (i << 1) + 1;
PRIMES[0] = j;
}
void __fastcall nextSieve(int beg, int end)
{
int p,i,j,k;
HIGHSQRT = (int)sqrt(end);
for ( i = 0; i < SIZE; i++ )
WorkCache[i] = BaseCache[i];
i = 8; p = 19;
while ( p <= LOWSQRT )
{
j = beg % p;
if (j != 0)
{
j = beg + p - j;
if (j % 2 == 0) j+=p;
} else j = beg;
j = (j - beg + 1) >> 1;
for ( k = j; k < SIZE; k+=p )
WorkCache[k] = 0;
p = PRIMES[++i];
}
while ( p <= HIGHSQRT )
{
j = (p * p - beg + 1) >> 1;
for ( k = j; k < SIZE; k+=p )
WorkCache[k] = 0;
p = PRIMES[++i];
}
LOWSQRT = HIGHSQRT;
}
int __fastcall PrimeCount(int len)
{
int c = 0,i;
for ( i = 0; i < len; i++ )
if (WorkCache[i]) c++;
return c;
}
int main()
{
int c,i,j,k;
clock_t t1 = clock(),t2;
initCache();
firstSieve();
c = PRIMES[0];
int beg = C17 + 1,end = (C17 << 1) - 1;
while ( end < 100000000 )
{
nextSieve(beg,end);
c += PrimeCount(SIZE);
beg += C17; end += C17;
}
end = 99999999;
nextSieve(beg,end);
c += PrimeCount((end - beg)>>1);
t2 = clock();
printf("--> time : %d\n",t2-t1);
printf("Prime Count: %d\n",c);
return 0;
}

呆梦又萌了一次

原理叙述如下
筛法的主要原理就是筛去已有素数的倍数，从而剩下的就是新的素数了，但是在具体实现上，会有如下的问题
1、计算机的内存是有限度的，所以在筛除数据的时候，可能遇到很大范围的数据与小的内存的矛盾。
2、不同的筛选策略决定着算法的速度。
3、保存大量数据与内存存储容量的矛盾，这个其实跟问题1有相似点。

问题3 数据保存策略
通常想到的保存策略是保存成正常形式，32位下4字节，
以1亿内素数为例，大概5M个，需要20M空间
那么有没有更小的保存方式呢？
1、简单形式的位数组，100M / 8 = 12.5M，缺点是需要解码位信息为素数
2,、考虑其实所有超过30的素数可以写成
30k + 1, 7, 11, 13, 17, 19, 23, 29形式，正好8个组成1个字节
于是可以1个字节保存30k 到30k + 29内素数，需要100M / 30 = 3.3M
由于前30个数1不是素数，2,5不包含在内，所以得特殊处理，这个是这个方法需要注意的
这个解码位信息的工作量大于简单位数组
如果仅仅是计数，不保存就是了，而且只要知道n的三次方根以下素数，就有方法计算n以内素数个数，这个在高德纳书上例题里有介绍

3、考虑保存相邻素数的间隔，
一定范围内的素数，相邻素数的间隔是有最大值的，于是我们可以考虑保存相邻素数的间隔，以1亿为例，相邻素数最大间隔不高于256，于是1个字节足够了，那么5M左右素数，5M空间是完全可以的，这个方法要略大于30k方法但是解码成素数的工作量是最小的，推荐这种方式。
这种方式有个问题，就是素数范围大了后，会遇到超过256间隔的相邻素数，这个如何处理呢？
如果仅仅是需求素数做进一步处理，比如分解等其实最简单的方法是插入相邻素数中间位置的的合数作为过渡
如果是严格的需要素数表，就不能这么做，必须增加间隔占字节数

以下是相邻素数最大间隔数据