求N以内的素数

题目描述
从键盘上输入一个正整数N(N<=100)，求N之内的素数

输入
正整数N

输出
0~N之间的素数，每个素数一行

样例输入 Copy
100
样例输出 Copy
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

筛选法求N以内的素数算法：
（1）挖去1；
（2）用下一个未被挖去的数P去除P后面各数，把P的倍数挖掉；
（3）检查P是否小于N的开方的整数部分，如果是，则返回2继续执行，否则就结束。
（4）剩下的数就是素数。

筛选法

#include<stdio.h>
int main()
{
	int N,i,j,k;
	int a[100]={0};//数组的下标看情况而定
	scanf("%d",&N);
	for(i=2;i<=10;i++)//计算2-10的倍数
	  for(j=2;j*i<N+1;j++)
		   a[i*j]=1;//合数的数组值定为1
	for(k=2;k<N+1;k++)
		if(a[k]==0) //输出素数
			printf("%d\n",k);
	return 0;
}

函数法

#include<stdio.h>
int main()
{
	int prime(int a);
	int N,i,k;
	scanf("%d",&N);
	for(i=2;i<=N;i++)
	{
	   k=prime(i);
	   if(k==1)
		   printf("%d\n",i);
	}
	printf("\n");
	return 0;
}
int prime(int a)
{
	int i;
	for(i=2;i<a;i++)
       if(a%i==0)break;
	if(i==a) return 1;
	else return 0;
}