leetcode Count Primes

leetcode Count Primes

Description:

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

题目地址 ： leetcode Count Primes

思路:

朴素的判断必定超时，我们每次判断一个数是素数的时候，就将它的倍数标记为非素数即可。

下面附上c++  python 和 java代码

Code

C++

class Solution {
public:
	int countPrimes(int n) {
		if (n <= 2) return 0;
		bool * isPrimer = new bool[n];
		for (int i = 0; i < n; i++)	isPrimer[i] = true;
		for (int i = 2; i * i < n; i++) {
			if (isPrimer[i])
				for (int j = i ; j * i < n; j ++)
					isPrimer[j * i] = false;
		}
		int res = 0;
		for (int i = 2; i < n; i++)
			if (isPrimer[i]) res++;
		delete[] isPrimer;
		return res;
	}
};

 

Java

class Solution {
    public int countPrimes(int n) {
        if (n <= 2) return 0;
        boolean[] vis = new boolean[n];
        for (int i = 2; i * i < n; i++) {
            if (vis[i]) continue;
            for (int j = i; j * i < n; j++)
                vis[i * j] = true;
        }
        int ans = 0;
        for (int i = 2; i < n; i++)
            if (!vis[i]) ans++;
        return ans;
    }
}

 

Python

class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 2: return 0
        vis = [False] * n
        for i in range(2, int(n ** 0.5) + 1):
            if vis[i]: continue
            j = i
            while j * i < n:
                vis[j * i] = True
                j += 1
        ans = 0
        for i in range(2, n):
            if not vis[i]: ans += 1
        return ans

 

更多题解可以查看： https://www.hrwhisper.me/leetcode-algorithm-solution/