篩減法求素數

這種方法的求素數的效率很高

#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]