FazBrowse GitHub Viewer | Trending | | Home

Tools: [Download Repo ZIP] [View Raw Code] [Original HTTPS Page]

LeetCode-Solutions/C++/count-primes.cpp at master · lightwindy/LeetCode-Solutions · GitHub

Repository navigation

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

// Time: O(n)

// Space: O(n)

class Solution {

public:

int countPrimes(int n) {

if (n <= 2) {

return 0;

}

auto num = n / 2;

vector<int> is_prime(n, true);

for (int i = 3; i * i < n; i += 2) {

if (!is_prime[i]) {

continue;

}

for (int j = i * i; j < n; j += 2 * i) {

if (!is_prime[j]) {

continue;

}

--num;

is_prime[j] = false;

}

}

return num;

}

};

Back | FazBrowse Home | New Git URL