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

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

编写一个C语言程序,实现用Eratosthenes筛选法求素数.

算法

(1)先把1删除(现今数学界1既不是质数也不是合数).

(2)读取队列中当前最小的数2,然后把2的倍数删去.

(3)读取队列中当前最小的数3,然后把3的倍数删去.

(4)读取队列中当前最小的数5,然后把5的倍数删去.

(5)如上所述直到需求的范围内所有的数均删除或读取.

代码实现

/*
*本代码版权归高小调博客所有 
*作者:高小调
*日期:2016-9-14
*代码功能:通过C语言实现Eratosthenes筛选法
*集成开发环境:Microsoft Visual Studio 2010 
*/
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
/*
*函数功能:通过筛选法得到从0到n的素数
*参数说明:arr,素数容器;n,范围的最大上限
*返回值:无
*/
void Eratosthenes(int *arr,int n){
    int i = 0;
    int j = 0;
	arr[0] = 0;
	arr[1] = 1;
    //假设所有的数都是素数 
    for(i=2;i<n;i++){
        arr[i] = 1;
    }
    for(i=2;i<n;i++){
        if(arr[i]==1){
        //如果i是素数 
            for(j=2;i*j<n;j++){
            //剔除掉i的倍数 
                arr[i*j]=0;
            }
        }else{
        //i之前已经被剔除掉了 
        } 
    }
}
//测试函数:求100-200之间的素数
void Test_Eratosthenes(int min,int max){
    int i = 0;
    int count = 0; 
    int *arr = NULL;
	if(min<0 || min>max){
		return ;
	}
	arr = (int *)malloc(sizeof(int)*max);
	if(!arr){
		printf("内存开辟失败!\n");
		exit(1);
	}
    Eratosthenes(arr,max);
    for(i=min;i<max;i++){
        if(arr[i]){
            printf("%d ",i);
            count++;
        }
    }
    printf("\ncount=%d\n",count);
	free(arr);
}
int main(){
    //求100-200之间的素数
    Test_Eratosthenes(100,200);
    system("pause");
    return 0;
}

输出结果

输出结果

在本次的实例中,每个素数都占用了1个字节,还存在优化的空间.

至于怎么优化...请看下篇文章:Eratosthenes筛选法求素数(二)

PS:最近有些忙...

上一篇:
下一篇: