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;
}