leecode 解题总结：204. Count Primes

#include <iostream>#include <stdio.h>#include <vector>#include <string>#include <unordered_map>using namespace std;/*问题:Description:Count the number of PRime numbers less than a non-negative number, n.分析:输出一个非负整数n中,<n的质数个数。这个明显用质数表格来做。质数：仅能被1和本身整除的数，0不是质数，1不是质数，2是质数，3是质数所谓质数表格，事先设定一个数组visited[n]中每个数初始都为质数标记true,然后从i=2开始遍历，令i < n, i++;设置 k = i * i ; k += i开始，每个k都设置为质数将所有的i设置为合数即可。输入:011020499979输出:0048关键:1 考虑 i * i 会溢出，限制i最多为sqrt(n)报错：溢出，没考虑n=0的情况，粗心输入499979，vector溢出。溢出了，用int不好，直接用bool，减少内存//关键是这里 i * i会溢出for(int k = i * i ; k < n ; k += i )*/class Solution {public:    int countPrimes(int n) {		if(n <= 1)		{			return 0;		}        vector<bool> primerFlags(n , true);//设置1表示质数 		int result = 0;		int upper = (int)sqrt(n);//一个数的素数最多不会超过upper		for(int i = 2 ; i < n ; i++)		{						//如果当前数为合数，不再进行后续访问			if(false == primerFlags[i])			{				continue;			}			//当前数为素数，累加			else			{				result++;			}			//防止 i * i溢出			if(i > upper)			{				continue;			}			//关键是这里 i * i会溢出			for(int k = i * i ; k < n ; k += i )			{				primerFlags[k] = false;//设置为合数			}		}		return result;    }};void process(){	 int num;	 Solution solution;	 while(cin >> num )	 {		 int answer = solution.countPrimes(num);		 cout << answer << endl;	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}