Leetcode——204. Count Primes

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

题目

Description:

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

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

Hint:

Let’s start with a isPrime function. To determine if a number is prime, we need to check if it is not divisible by any number less than n. The runtime complexity of isPrime function would be O(n) and hence counting the total prime numbers up to n would be O(n2). Could we do better?

Show More Hint

解答

寻找小于一个数的所有质数（素数：prime）

Two methods.

1. traverse the number from 2 to n, judge whether the number is prime or not.
   
   1. How we know whether the number is a prime?
   2. if the number is divisible by one of the number from 2 to n/2(sqrt(n)), it is not prime, if not, it is prime.
   3. The complexity is O(N^2) or O(N^1.5)
2. The second amazing method is Sieve of Eratosthenes!!!
   
   1. Create a list of consecutive integers from 2 through n:(2,3,4,…,n)
   2. Initially, let p equal 2,the smallest prime number.
   3. Enumerate the multiples of p by counting to n from 2p in increments of p, and mark them in the list(these will be 2p,3p,4p,…; the p iteself should not be marked).
   4. Find the first number that is greater than p in the list that is not marked, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.

Code:

class Solution1 {//O(N^2)
public:int countPrimes(int n) {int count=0;if(n==1) return 0;for(int i=2;i<n;i++)if(isPrime(i))count++;return count;}
private:bool isPrime(int n)//judge whether n is a prime number or not{for(int i=2;i<=n/2;i++){if(n%i==0) return false;}return true;}
};
class Solution2 {//O(N^1.5)，也是超时
public:int countPrimes(int n) {int count=0;if(n==1) return 0;for(int i=2;i<n;i++)if(isPrime(i))count++;return count;}
private:bool isPrime(int n)//judge whether n is a prime number or not{for(int i=2;i<=sqrt(n);i++){if(n%i==0) return false;}return true;}
};

class Solution3 {// Sieve of Eratosthenes. https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
public:int countPrimes(int n) {if(n<2) return 0;int count=0;bool isPrime[n]={0};//0 represents the number is primefor(int p=2;p<n;p++){if(!isPrime[p]){count++;for(int j=p*2;j<n;j+=p){isPrime[j]=true;}}}return count;}};
class Solution {// Sieve of Eratosthenes. https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
public:int countPrimes(int n) {if(n<=2) return 0;int count=0;bool isPrime[n]={0};//0 represents the number is primefor(int p=2;p<n;p++){if(!isPrime[p]){count++;if(p>sqrt(n)) continue;for(int j=p*p;j<n;j+=p){isPrime[j]=true;}}}return count;}};

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

---