C语言::Eratosthenes筛选法求素数(二) - 高小调博客

C语言::Eratosthenes筛选法求素数(二)

本文通过按位存储的方式,实现对Eratosthenes筛选法的进一步优化,提高空间的利用率.(代码较长,就不进行分段了)

SetBit()、ClearBit()、AssignBit()、GetBit()等函数实现位数组的相关操作.

EratosthenesBit()函数实现筛选法

PS:虽然AssignBit()函数在本实例中没有用到,但我还是把它贴了出来...

这次就不多说废话,一切言语尽在注释中,有疑问的兄弟,可以在底下留言.

代码实现

/*
*本代码版权归高小调博客所有 
*作者:高小调
*日期:2016-9-14
*代码功能:C语言实现Eratosthenes筛选的优化
*集成开发环境:Microsoft Visual Studio 2010 
*/
#include<stdio.h>
#include<assert.h>
#include<malloc.h>
#include<stdlib.h>
//位数组的结构
//bit_arr[0] bit_arr[1] 实际字符数组
//00000000   0000000000 位数组值
//01234567   89...	位数组下标
/*
*函数功能:把位数组中指定的位改为1 
*参数说明:bit_array,位数组;bit_number,下标访问的位 
*返回值:无返回值 
*/
void SetBit(char bit_array[],unsigned int bit_number){
	int arr_pos = bit_number/8;
	int bit_pos = (7-(bit_number%8));
	int tmp = 1;
	assert(bit_array);
	*(bit_array+arr_pos) |= (tmp<<bit_pos);
}
//测试函数 
void Test_SetBit(){
	char arr = 0;
	//0000 0000
	//0
	printf("%d\n",arr);
	SetBit(&arr,0); 
	//1000 0000 
	//-128 
	printf("%d\n",arr);
	SetBit(&arr,4); 
	//1000 1000
	//-120
	printf("%d\n",arr);
	SetBit(&arr,7);
	//10001001
	//-119
	printf("%d\n",arr);
}
/*
*函数功能:把位数组中指定的位清0 
*参数说明:bit_array,位数组;bit_number,下标访问的位 
*返回值:无返回值 
*/
void ClearBit(char bit_array[],unsigned int bit_number){
	int arr_pos = bit_number/8;
	int bit_pos = (7-(bit_number%8));
	int tmp = 1;
	assert(bit_array);
	*(bit_array+arr_pos)&= (~(tmp<<bit_pos));
}
//测试函数 
void Test_ClearBit(){
	char arr = 0;
	printf("%d\n",arr);
	SetBit(&arr,0);
	printf("%d\n",arr);
	SetBit(&arr,4); 
	printf("%d\n",arr);
	SetBit(&arr,7);
	printf("%d\n",arr);
	ClearBit(&arr,7);
	printf("%d\n",arr);
	ClearBit(&arr,4);
	printf("%d\n",arr);
	ClearBit(&arr,0);
	printf("%d\n",arr);
}
/*
*函数功能:把位数组中指定的位赋值为指定的值 
*参数说明:bit_array,位数组;bit_number,下标访问的位;value,指定的值 
*返回值:无返回值 
*/
void AssignBit(char bit_array[],unsigned int bit_number,int value){
	int arr_pos = bit_number/8;
	int bit_pos = (7-(bit_number%8));
	int tmp = 1;
	assert(bit_array);
	if(value){
		//置1 
		*(bit_array+arr_pos) |= (tmp<<bit_pos);
	}else{
		//置0 
		*(bit_array+arr_pos) &= (~(tmp<<bit_pos));
	}
}
//测试函数
void Test_AssignBit(){
	char arr = 0;
	printf("%d\n",arr);
	AssignBit(&arr,0,1);
	printf("%d\n",arr);
	AssignBit(&arr,4,1);
	printf("%d\n",arr);
	AssignBit(&arr,7,1);
	printf("%d\n",arr);
	AssignBit(&arr,7,0);
	printf("%d\n",arr);
	AssignBit(&arr,4,0);
	printf("%d\n",arr);
	AssignBit(&arr,0,0);
	printf("%d\n",arr);
}
/*
*函数功能:判断指定位的值
*参数说明:bit_array,位数组;bit_number,下标访问的位;value,指定的值 
*返回值:非零返回真,否则返回假 
*/
int GetBit(char bit_array[],unsigned int bit_number){
	int arr_pos = bit_number/8;
	int bit_pos = (7-(bit_number%8));
	assert(bit_array);
	return ((*(bit_array+arr_pos))>>bit_pos)&1;
}

//测试函数
void Test_GetBit(){
	char arr = 0;
	SetBit(&arr,7);
	printf("%d\n",GetBit(&arr,7));
	ClearBit(&arr,7);
	printf("%d\n",GetBit(&arr,7));
}
/*
*函数功能:Eratosthenes筛选法得到素数
*参数说明:bit_arr[],位数组;n,求素数的范围上限 
*返回值:无返回值 
*/ 
void EratosthenesBit(char bit_arr[],int n){
	int i = 0;
	int j = 0;
	assert(bit_arr);
	//把0和1剔除 
	ClearBit(bit_arr,0);
	ClearBit(bit_arr,1);
	//给其他元素置1 
	for(i=2;i<n;i++){
		SetBit(bit_arr,i);
	}
	//开始筛选 
	for(i=2;i<n;i++){
		if(GetBit(bit_arr,i)){
			//如果i是素数 
			for(j=2;i*j<=n;j++){
				//剔除所有i倍的数 
				ClearBit(bit_arr,i*j);
			}
		}else{
			//i不是素数(已经被筛选掉了) 
		} 
	}
}
/*
*函数功能:根据所给范围利用筛选法获得素数序列 
*参数说明:left,素数范围下限;right,素数范围上限 
*返回值:无返回值
*/ 
void GetPrime(unsigned int left,unsigned int right){
	int i = 0;
	int count = 0;
	char *bit_arr = NULL;
	if(left<0||right<left){
		return ;
	}
	//根据参数动态开辟一段空间 
	bit_arr = (char *)malloc(sizeof(char)*((right/8)+1));
	//空间开辟失败 
	if(!bit_arr){
		printf("动态内存开辟失败,程序自动退出\n");
		exit(1);
	}
	//进行筛选 
	EratosthenesBit(bit_arr,right);
	//输出参数范围内的素数 
	for(i=left;i<right;i++){
		if(GetBit(bit_arr,i)){
			printf("%d ",i);
			count++;
		}
	}
	printf("\ncount=%d\n",count);
	//释放掉内存 
	free(bit_arr);
}

int main(){
	//Test_SetBit();
	//Test_ClearBit();
	//Test_AssignBit();
	//Test_GetBit();
	GetPrime(1,2000);
	system("pause");
	return 0;
}

输出结果

好好学习,天天向上!!!

上一篇:
下一篇: