筛减法求素数

这种方法的求素数的效率很高

#include <stdio.h>
#include <stdlib.h> 

/*筛选法求素数,即质数 
	素数是只能被1和自身整除的数 
	从2开始递增，删除此数的倍数，则以后出现的就都是素数了 
*/

int main(int argc, char *argv[])
{
	//atoi函数将字符串转化为长整型 
	int i, j, N = atoi(argv[1]);
	int *a = malloc(N * sizeof(int)); 
	//初始化 
	for (i = 0; i < N; i++)	a[i] = 1;
	for (i = 2; i < N; i++)
		if (a[i])
			for (j = i; j <= N/i; j++)	a[i*j] = 0;
	for (i = 2; i < N; i++)
		if (a[i])	printf("%4d ", i);
	printf("\n");
} 

执行如下：

[img]http://dl.iteye.com/upload/attachment/508348/0315b881-113d-3894-870d-ae0b1f04ac2d.bmp[/img]