leetcode No204. Count Primes

本文主要是介绍leetcode No204. Count Primes，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Question

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

Algorithm

筛法求素数

Accepted Code

python

class Solution(object):def countPrimes(self, n):if n<3:return 0primes = [True]*nprimes[0] = primes[1] = Falsefor i in range(2,int(n ** 0.5)+1):    # **代表乘方if primes[i]:j = i*2;while(j < n):primes[j] = Falsej = j+ireturn sum(primes)

C++

class Solution {
public:int countPrimes(int n) {if(n<3)return 0;vector<bool> v(n,true);for(int i=2;i<=sqrt(n);i++){for(int j=i*2;j<n;j+=i){v[j]=false;}}int res=0;for(int i=2;i<n;i++){if(v[i]==true)res++;}return res;}
};

这篇关于leetcode No204. Count Primes的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---