打印质数表

题目描述
输入一个自然数N，按质数定义从小到大输出1~N（包含N）中所有的质数

输入描述:
输入一行，包含一个整数N
1 <= N <= 2000

输出描述:
输出一行，包含所有的质数，按照从小到大的顺序输出，以空格隔开。

示例1
输入：20
输出：2 3 5 7 11 13 17 19

解题思路：
思路一：对 [1, n] 的每个数进行判断是否为质数。对单个数 x ，枚举 [2, sqrt(x)] 区间的整数，若均无法被 x 整除，则 x 为质数。判断质数的时间复杂度为 ，整体时间复杂度为 ，空间复杂度为 。
思路二：使用长度为 N+1 的布尔型数组 p ，p[i] 为真表示 i 是质数，反之，i 不是质数。同样对 [1, n] 的每个数 i 进行判断，但，是判断是否为非质数，若 i 为非质数则判断 i+1，否则对 i 到 n 进行枚举，必然有 i * i、i * (i+1)、...、i * (i+k) 是非质数。外循环时间复杂度为 ，内循环时间复杂度为 ，总体时间复杂度 ，空间复杂度 。
内循环复杂度的大致计算即对每次 i 进行展开的枚举次数 k ：由于 i * (i+k) ≤ n，因此， ，该级数的极限为 。

思路二 C# 代码：

using System;
class Program
{
  static void Main()
  {
      string input;
      while ((input = Console.ReadLine()) != null)
      {
          int n = int.Parse(input);
          bool[] p = new bool[n+1];
          Array.Fill(p, true, 2, n-2);
          for(int i = 2; i <= n; i++){
              if(!p[i]) continue;
              for(int j = i*i; j <= n; j += i) p[j] = false;
          }
          for(int i = 2; i <= n; i++) if(p[i]) Console.Write(i + " ");
      }
  }
}