素数筛选

今天在面试时被问到了一个问题：求不大于n的最大素数，当时只想出暴力解法，回来查资料找到了正确的求解方法。

素数筛法是这样的：
1. 开一个大的bool型数组prime[]，大小就是n+1就可以了.先把所有的下标为奇数的标为true,下标为偶数的标为false.

vector<bool> prime(n+1, true);
for(int i=0; i<n+1; ++i)
  if(i%2 == 0)
    prime[i] = false;

2. 然后：

      for(int i=3; i<=sqrt(n); i+=2)
      {   if(prime[i]) 
          for( j=i+i; j<=n; j+=i ) prime[j]=false;
      }

3.最后输出bool数组中的值为true的单元的下标，就是所求的n以内的素数了。

背后的原理是：当i是素数的时候，i的所有的倍数必然是合数。如果i已经被判断不是质数了，那么再找到i后面的质数来把这个质
数的倍数筛掉。