leetcode-204-Count-Primes

发表于   |  

描述

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.

分析

题意是找到小于n的质数的个数，如果是用常规方法判定，肯定会超时，其实可以采用厄拉托斯特尼筛法，先用2筛选，把2的倍数筛掉，再用下一个质数3，把3的倍数筛掉，接下来是5，把5的倍数筛掉，不断重复，直到$\sqrt{n}$

解决方案1(C++)

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
28
29
30
31
class Solution {
public:
    int countPrimes(int n) {
        bool *result = new bool[n];
        result[2] = false;
        int count = 0;
        
        for(int i = 3; i < n; i++) {
            if(i % 2 == 0) {
                result[i] = true;
            }else {
                result[i] = false;
            }
        }
        
        for(int i = 3; i*i < n; i += 2) {
            if(!result[i]) {
                for(int j = 2; i*j < n; j++) {
                    result[i*j] = true;
                }
            }
        }
        
        for(int i = 2; i < n; i++) {
            if(!result[i]) {
                count++;
            }
        }
        return count;
    }
};

相关问题

题目来源