Count Primes

Description:

Count the number of prime numbers less than a non-negative number, n

解题思路：

题意为求小于n的质数的个数。有两种方法：

1、naive办法，对小于n的每个数，检查是否为质数。而检查m是否为质数，需要验证是否都不能被2~pow(m, 0.5)整除。这个方法的时间复杂度为O(n^2)，空间复杂度为O(1)。会产生超时错误。

class Solution {
public:
    int countPrimes(int n) {
        int count=0;
        for(int i=0; i
2、用一个数组来标记是否为质数。大体思想是：2是质数，那么2的所有倍数（除本身）都不是质数，此时标记2的所有倍数（除本身）为非质数。从小到大扫描，若当前扫描的是质数，则标记其所有的非本身的倍数为非质数。最后对所有质数计数即可。下面为代码：
class Solution {
public:
    int countPrimes(int n) {
        if(n<2){
            return 0;
        }
        
        bool primFlag[n];
        
        memset(primFlag, 1, sizeof(bool) * n);
        
        primFlag[0]=primFlag[1]=false;
        
        double up = pow(n, 0.5);
        
        for(int i=2; i
这个算法的空间复杂度为fO(n)，时间复杂度比较复杂。该方法称为Eratosthenes算法。
3、算法2的改进：
class Solution {
public:
    int countPrimes(int n) {
        if(n<2){
            return 0;
        }
        
        bool primFlag[n];
        
        memset(primFlag, 1, sizeof(bool) * n);
        
        primFlag[0]=primFlag[1]=false;
        
        double up = pow(n, 0.5);
        
        int count=n-2;
        
        for(int i=2; i

 
转载请注明： » [LeetCode] Count Primes

<!--
                    

                    	

                        	

                            	
                            
                        
                        

                        	

                            	
相关博文：
                                

                                	
                                    	
                                        	
                                        
                                        
定制桌面成功案例
                                    
                                    
                                    	
                                        	
                                        
                                        
海量文档查同或聚类问题 -- Locality Sensitive Hash 算法 （转）
                                    
                                    
                                    	
                                        	
                                        
                                        
汉字转拼音c/c++源码，支持gb2312和utf8
                                    
                                    
                                    	
                                        	
                                        
                                        
数据库顶级会议——SIGMOD介绍
                                    
                                
                            
                        
                    
                    -->