欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode 204. Count Primes

程序员文章站 2024-03-21 15:06:10
...

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

Example:

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Sieve of Eratosthenes算法图解:

LeetCode 204. Count Primes

C++

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

Java

class Solution {
    public int countPrimes(int n) {
        boolean[] isPrim = new boolean[n];
        Arrays.fill(isPrim, true);
        for(int i = 2; i * i < n; i++){
            if(isPrim[i]){
                for(int j = i * i; j < n; j += i){
                    isPrim[j] = false;//排除所有质数的倍数
                }
            }
        }
        int cnt = 0;
        for(int i = 2; i < n; i++){
            if(isPrim[i]) cnt++;
        }
        return cnt;
    }
}

Python

class Solution(object):
    def countPrimes(self, n):
        if n < 3:
            return 0
        primes = [True] * n
        primes[0] = primes[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if primes[i]:
                primes[i * i: n: i] = [False] * len(primes[i * i: n: i])
        return sum(primes)

上一篇: KITTI数据集介绍

下一篇: