质数数量

题目描述
质数（prime number）又称素数，有无限个，质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。例如小于10的质数有2，3，5，7。

输入描述:
第一行输入一个整数T，表示询问的个数
接下来T行每行输入一个整数n.
1<=T<=1e8,1<=n<=1000000

输出描述：
对于每个询问n输出小于等于n的的质数的个数。

示例1
输入：
2
10
1000000
输出：
4
78498

注意

尽管不太清楚通过的代码是怎么通过的，但是在这之前我使用C#进行提交的时候发现总是在第二个测试用例出错，因此向工作人员进行了反映后确实是第二个测试用例有问题，并且也已经得到了修复，因此下述代码可AC。

解题思路：
这道题与打印质数表 相似，只是一个是打印出质数，一个是输出质数的数量，因此可以使用打印质数表题解 中的思路，并且也应该按此思路进行。因为给定的输入数值的范围过大，若是在循环读取输入数据中进行求解碰到大数值的输入很容易超时。因此在循环读数之前先用一个大数组记录小于等于 n 的质数的数量。
定义 cnt 为长度为1000001的一维数组，其中 cnt[i] 表示小于等于 i 的质数数量，并利用打印质数表题解 中的思路，将1000000以内为质数的数用长度为1000001的一维布尔数组 p 表示，其中 p[i] 为真表示 i 为质数，反之 i 不为质数，并枚举 p[i] ，将小于等于 i 的质数数量存入 cnt[i] 中。
具体为：若 p[i] 为真，则 cnt[i] = cnt[i-1] + 1，反之 cnt[i] = cnt[i-1]。即 p[i] 不为真，则小于等于 i 的质数数量与小于等于 i-1 的质数数量相等。则预处理完之后，在进行循环读数时，读入数值 n 则对应的结果为 cnt[n]。

C# 代码：

using System;
class Program{
  static void Main(){
      bool[] p = new bool[1000001];
      int[] cnt = new int[1000001];
      Array.Fill(p, true);
      for(long i = 2; i <= 1000000; i++){
          if(!p[i]) continue;
          for(long j = i*i; j <= 1000000; j += i) p[j] = false;
      }
      for(int i = 2; i <= 1000000; i++) 
          cnt[i] = p[i] ? cnt[i-1] + 1 : cnt[i-1];

      string input;
      while((input = Console.ReadLine()) != null){
          int T = int.Parse(input);
          for(int i = 1; i <= T; i++){
              input = Console.ReadLine();
              int n = int.Parse(input);
              Console.WriteLine(cnt[n]);
          }
      }
  }
}