leetcode 204. 计数质数

叁歲伎倆 2023-06-04 09:54 126阅读 0赞

**筛法，从一个质数的2倍开始依次筛去合数，不够优化**

class Solution { 
    public:
        int countPrimes(int n) { 
            if( n<2 ){ 
                return 0;
            }
            bool *pri = new bool[n+1];
    
            fill( pri,pri+n+1,1 );
    
            for( int i = 2;i < n;i++ ){ 
                if(pri[i]){ 
                    for( int j=2;i*j<n; j++ ){ 
                        pri[i*j] = 0;
                    }
                }
            }
            int cnt = 0;
            for( int i=2;i<n;i++ ){ 
                if( pri[i] ){ 
                    cnt++;
                }
            }
            return cnt;
        }
    };

![在这里插入图片描述][2019100721423495.png]

**外层循环改为根号n**

class Solution { 
    public:
        int countPrimes(int n) { 
            if( n<2 ){ 
                return 0;
            }
            bool *pri = new bool[n+1];
    
            fill( pri,pri+n+1,1 );
            int sq = (int)sqrt(n) + 1 ;
            for( int i = 2;i <= sq ;i++ ){ 
                if(pri[i]){ 
                    for( int j=2; i*j<= n; j++ ){ 
                        pri[i*j] = 0;
                    }
                }
            }
            int cnt = 0;
            for( int i=2;i<n;i++ ){ 
                if( pri[i] ){ 
                    cnt++;
                }
            }
            return cnt;
        }
    };

![在这里插入图片描述][2019100819262420.png]

**内层循环从i \* i开始，因为i\*(i-1)在i-1的时候已经乘过i了**

class Solution { 
    public:
        int countPrimes(int n) { 
            if( n<2 ){ 
                return 0;
            }
            bool *pri = new bool[n+1];
    
            fill( pri,pri+n+1,1 );
            int sq = (int)sqrt(n) + 1 ;
            for( int i = 2;i <= sq ;i++ ){ 
                if(pri[i]){ 
                    for( int j= i*i ; j<= n; j+=i ){ 
                        pri[j] = 0;
                    }
                }
            }
            int cnt = 0;
            for( int i=2;i<n;i++ ){ 
                if( pri[i] ){ 
                    cnt++;
                }
            }
            return cnt;
        }
    };

![在这里插入图片描述][20191008195113903.png]  
**虽然看起来时间没少多少，但是可能是数据量少吧，有时候居然会比第二个慢**

[2019100721423495.png]: /images/20230601/d2ecf50251d34fb09d336b81e0cc049a.png
[2019100819262420.png]: /images/20230601/28f62cda87394532ba3effe140ac5993.png
[20191008195113903.png]: /images/20230601/5f9c5432516144cfaa4238bdd06edd41.png