Problem Description
用筛法求之N内的素数。
Input
N
Output
0～N的素数
Sample Input
100
Sample Output
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
步骤举例：
详细列出算法如下：
- 列出2以后的所有序列：
- 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
- 标出序列中的第一个素数，也就是2，序列变成：
- 23 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
- 将剩下序列中，划摽2的倍数（用删除线标出），序列变成：
- 2 34567 891011 12 13 14 15 16 17 18 19 20 21 22 23 24 25
- 如果现在这个序列中最大数小于最后一个标出的素数的平方，那么剩下的序列中所有的数都是素数，否则回到第二步。
- 本例中，因为25大于2的平方，我们返回第二步：
- 剩下的序列中第一个素数是3，将主序列中3的倍数划出（删除线），主序列变成：
- 2 3 4 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
- 我们得到的素数有：2，3
- 25仍然大于3的平方，所以我们还要返回第二步：
- 现在序列中第一个素数是5，同样将序列中5的倍数划出，主序列成了：
- 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
- 我们得到的素数有：2 3 5 。
- 因为25等于5的平方，跳出循环.
结论：去掉划线的数字，2到25之间的素数是：2 3 5 7 11 13 17 19 23。
#include<iostream>
using namespace std;
int main()
{
int i,j,n,a[1000];
cin >> n;
for(int i = 1;i <= n;i++)
{
a[i] = i; //将1~n储存在数组a[i]中
}
for(int i = 2;i < n;i++)
{
for(int j = i + 1;j < n;j++)
{
if(a[i] != 0 && a[j] != 0)
{
if(a[j]%a[i] == 0)
a[j] = 0;//若a[i]不是素数，令a[i]=0;
}
}
}
for(int i = 1;i < n;i++)
{
if(a[i] != 0 && a[i] != 1)
{
cout << a[i] << endl;
}
}
return 0;
}
