首页 > 代码库 > Leetcode problem-204 Count Primes 题解

Leetcode problem-204 Count Primes 题解

Leetcode problem-204 Count Primes

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

题解:这道题如果对每个小于n的数都进行判断是否为素数并计数会超时,因此采用筛法来解这题。建一个数组,从2开始, 把其倍数小于N的都删掉。

class Solution {

public:

    int countPrimes(int n) {

        vector<int>arr(n,1);

        int sum=0;

        for(int i=2;i<=n;i++)

        {

            if(arr[i]==1)

            {

                sum++;

                for(int j=i;j<n;j+=i)

                {

                    arr[j]=0;

                }

            }

 

        }

        return sum;

    }

};

Leetcode problem-204 Count Primes 题解