埃氏筛法求素数

埃氏筛法求素数

知识介绍：

埃氏筛法，全名埃拉托斯特尼筛法，也叫爱氏筛法，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。

底层概念：

一个数的倍数必不为素数。

算法思路：

先将所有数初始化为素数，再通过概念数的倍数不为素数，剔除不是素数的数，并计数，最后输出。

代码如下：

#include
#include

int main()
{
	printf("请输入你要求的素数在什么范围以内：");
	
	int n ;
	scanf("%d" , &n);
	
	int s[n + 1];									//定义数组大小；加一防止超过数组上限
	int count = 0 ; 								//定义计数器
	
	for( int i = 0 ; i <= n ; i ++){
		s[i] = 1 ;									//初始状态将所有书定义为素数
	}
	
	for( int i = 2 ; i <= sqrt (n) ; i ++){         //此处调用求根函数sqrt
		if( s[i] == 1){
			for( int j = i*i ; j <= n ; j += i){	//任何数的倍数都不为素数
				s[j] = 0;							//剔除
			}		
		}
	}
	
	for( int i = 2 ; i <= n ; i ++){
		if(s[i] == 1){
			printf("%6d" , i);					//若为素数输出并计数
			count ++;
			
			if(count % 5 == 0)printf("n");		//为了方便观看结果适当换行
		}
	}
	
	printf("nt素数有 %d 个" , count);
	
	return 0;
	
}

结果如下：