筛法求素数

筛法求素数

时间: 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);
}

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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注