LeetCode: 204. Count Primes

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

204. Count Primes

LeetCode - Count Primes

如何实现一个高效的筛选法？

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Runtime: 163 ms, faster than 25.96% of Java online submissions for Count Primes.
 *
 * Memory Usage: 93.7 MB, less than 5.66% of Java online submissions for Count Primes.
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2020-01-10 23:04
 */
public int countPrimes(int n) {
    if (n < 3) {
        return 0;
    }
    Set<Integer> numbers = new HashSet<>();
    numbers.add(2);
    for (int i = 3; i < n; ) {
        numbers.add(i);
        i += 2;
    }
    for (int i = 3; i < Math.sqrt(n); ) {
        for (int j = 3; i * j < n; ) {
            numbers.remove(i * j);
            j += 2;
        }
        i += 2;
    }
    return numbers.size();
}