筛法求素数

筛法求素数

时间： 1ms        内存：128M

描述：

用筛法求之N(1<N<=10000000)内的素数。

输入：

N

输出：

0～N的素数

示例输入：

100

示例输出：

2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97

提示：

参考答案（内存最优[748]）：

#include <stdio.h>
void prim(int n){
	int i,j,a[n];  
	for(i=2;i<n;i++)  
	{ 	a[i]=i;  
		for(j=2;j<=i;j++)  
		{
			if(j<i)  
			 if(a[i]%j==0)  
			 break;  
			if(a[i]-j==0)  
			 printf("%d\n",a[i]);  
		}  
	} 	
}
main()  
{  
	int  a;
	scanf("%d",&a);
	prim(a);
}

参考答案（时间最优[0]）：

#include <stdio.h>
void prim(int n){
	int i,j,a[n];  
	for(i=2;i<n;i++)  
	{ 	a[i]=i;  
		for(j=2;j<=i;j++)  
		{
			if(j<i)  
			 if(a[i]%j==0)  
			 break;  
			if(a[i]-j==0)  
			 printf("%d\n",a[i]);  
		}  
	} 	
}
main()  
{  
	int  a;
	scanf("%d",&a);
	prim(a);
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。