欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Eratasthene筛选法求质数

程序员文章站 2024-03-14 20:41:53
...

【820复试题】用Eratasthene筛选法求质数

Eratasthene筛选法原理是通过空间换时间,求N个数以内的质素,先申请N个空间大小的数组,通过不断对2,3,4…sqrt(N)的倍数进行删除,最后输出剩下数字。

C代码如下:

#include<stdio.h>
#include<math.h>
#define N 200
int main() {
	//申请大小为N+1的数组空间,使数组下标与实际序号对应
	//数组arr中值为1表示该数不为质数,值为0为质数
	int arr[201] = {0};
	for (int d = 2; d <= sqrt(200);d++) 
	{
		for (int i = 2*d; i <= 200; i++)
			//依次删除d的倍数,从d的2倍开始到200
			 if (i % d == 0)
				arr[i] = 1; 
	}
	//从2开始输出剩余质数
	for (int k=2 ;k <= 200; k++)
		if (arr[k] == 0) 
			//输出没有被删除的数
			printf("%d\t",k);
				
	return 0;
}