Egbert Lin's Blog

“Life is not a race, but a journey to be savoured each step of the way” by Brian Dyson

[LeetCode Road] Count Primes - Solution/C++

Posted on Edited on In Disqus:

204. Count Primes

Question:

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

Example:

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

Input: n = 0
Output: 0

Input: n = 1
Output: 0

Constraints:
  • 0 <= n <= 5 * 106

    • Source code

    Version 1

    Idea:
    If you looked at source code, you must feel so easy.
    At first, give a statement if n is smaller than 2, return 0.

    Declare a vector that the size is n, variable of count as output and variable of i as vector's index.

    i starts at 2, if vector[i] is 0, count will add 1. Then, get all multiples of the value of vector[i] but smaller than n, assign 1 to those position at vector.

    Notice: Assign 1 to vector[multiples of i] that means the value is not prime number
    So, if the value of vector[i] is 0, it's must prime number.

    The demonstration is shown as below:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution {
    public:
        int countPrimes(int n) {
            if(n < 2) return 0;
            
            vector<int> number(n, 0);
            int count = 0, i = 2;
            while(i < n){
                if(number[i] == 0){
                    count++;
                    for(int j = 2; j*i < n; j++)
                        number[j*i] = 1;
                }
                i++;
            }
            return count;
        }
    };