筛法配合Bit位存储找素数

首先是未优化前的普通筛法版本

PS:测试而已，未按标准规范书写代码.

// shaifa.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <stdio.h>
#define MaxValue 40001  // 这里填写比范围大一.
bool Prime[MaxValue] ;
int su[MaxValue], count = 0;


int main()
{
    for (int i = 0; i <MaxValue; i++)
    {
        Prime[i] = true;
    }

    Prime[0] = Prime[1] = 0;  //0和1不是素数
    for (int i=0;i<MaxValue;i++)
    {
        if (Prime[i])
        {
            su[count++] = i;
                        // // 每次+i,也就是加一倍
			for (int t = i * 2; t <MaxValue; t += i)  
			{      
				Prime[t] = false;  // 筛掉倍数
			}
        }
    }
    for (int i=0;i<count;i++)
    {
        printf("%d\t", su[i]);
    }
}

优化版本

使用Bit位存储，通过 Num/8取得下标，再配合Num%8定位具体Bit位。

#include <stdio.h>
#define MaxValue 40001  // 这里填写比范围大一.
char Prime[MaxValue/8+ 1] ;
int su[MaxValue], count = 0;


int main()
{
    int x;
    for (int i = 0; i <MaxValue; i++)
    {
        Prime[i/8] = Prime[i / 8] | (1 << (i % 8));
    }
    //0和1不是素数
    Prime[0]= ((1 << 0) ^ 0xff)&Prime[0] ;
    Prime[0] = ((1 << 1) ^ 0xff) & Prime[0];
    for (int i=0;i<MaxValue;i++)
    {
        if ((Prime[i / 8] >> (i % 8))&0x1 )
        {
            su[count++] = i;
			for (int t = i * 2; t <MaxValue; t += i)  // 每次+i,也就是加一倍
			{
                Prime[t/8] = ((1 << (t%8)) ^ 0xff)& Prime[t/8];  // 筛掉倍数
			}
        }
    }
    for (int i=0;i<count;i++)
    {
        printf("%d\t", su[i]);
    }
}