用筛法求之N内的素数。 （C语言代码）

解题思路:使用了普通筛选法和线性筛选法。两者的时间复杂度不一样。

参考代码:

普通筛选法：时间复杂度是O(nloglogn)，不足之处在于一个合数可能被筛选多次。

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
int main()
{
	int n,i,j;
	char *p;
	scanf("%d",&n);
	if(n<2) return 0;
	p=(char *)malloc(n+1);
	memset(p,0,n+1);
	for(i=2;i<=n*n;i++)
	{ 
		if(p[i]==0)
			for(j=2;i*j<=n;j++)
				p[i*j]=1;
	} 
	for(i=2;i<=n;i++)
		if(p[i]==0)
			printf("%d\n",i);
	free(p);
	return 0;
}

线性筛选法：时间复杂度为O(n)，原因在于每个合数保证只被它最小的那个质因子筛选。关键代码在第17，18,19行，因为如果i能整除prime[j]，那么i肯定是个合数，且i中有质因子肯定小于等于prime[j]，所以到此就可以停止了，因为后面的prime[]会比i小的那个质因子要大。

#include <stdio.h>
#define N 10000+1 
int prime[N];
int main()
{
	int n,i,j,cnt=0;
	char tag[N];
	scanf("%d",&n);
	if(n<2) return 0;
	memset(tag,0,N);
	for(i=2; i<=n; i++)
	{		
		if(tag[i]==0)			
			prime[cnt++]=i;		
		for(j=0;j<cnt && prime[j]*i<=n; j++)
		{			
			tag[i*prime[j]] = 1;			
			if(i % prime[j]==0)				
				break;		
		}
	}
	for(i=0;i<cnt;i++)
		printf("%d\n",prime[i]);
	return 0;
}