Algorithm

[LeetCode 204] Happy Number [Java] [Beat: 91.09%]

顿搜

2017-09-02

0 评论

740 阅读

正在检测是否收录...

09/02

1. Description

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

2. Runtime Distribution

3. Submission Details

4. Example

Input 5
Output 2

5. Code

public int countPrimes(int n) {
    if (n < 3) {
        return 0;
    }

    boolean[] primes = new boolean[n];
    int sqrt = (int) Math.ceil(Math.sqrt(n - 1));
    for (int i = 2; i <= sqrt; i++) {
        if (primes[i]) {
            continue;
        }
        for (int j = i + i; j < n; j += i) {
            primes[j] = true;
        }
    }

    int count = 0;
    for (int i = 2; i < n; i++) {
        if (!primes[i]) {
            count++;
        }
    }
    return count;
}

6.Test

public class LeetCode0204 {
    public int countPrimes(int n) {
        if (n < 3) {
            return 0;
        }

        boolean[] primes = new boolean[n];
        int sqrt = (int) Math.ceil(Math.sqrt(n - 1));
        for (int i = 2; i <= sqrt; i++) {
            if (primes[i]) {
                continue;
            }
            for (int j = i + i; j < n; j += i) {
                primes[j] = true;
            }
        }

        int count = 0;
        for (int i = 2; i < n; i++) {
            if (!primes[i]) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        LeetCode0204 leetcode = new LeetCode0204();
        System.out.println(leetcode.countPrimes(5));
    }
}

Math

朗读