Count Primes

Problem

Given an integer n, return the number of prime numbers that are strictly less than n.

Example 1:

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

Example 2:

Input: n = 0
Output: 0

Example 3:

Input: n = 1
Output: 0

Constraints:

• 0 <= n <= 5 * 10^6

Hint

• Hint #1 : Checking all the integers in the range [1, n - 1] is not efficient. Think about a better approach.
• Hint #2 : Since most of the numbers are not primes, we need a fast approach to exclude the non-prime integers.
• Hint #3 : Use Sieve of Eratosthenes.

Solution

• 그냥 for loop을 사용할 경우, TLE 나온다
• Sieve Of Eratothons를 이용한다
  • 2의 배수를모두 지우고, 3의 배수를 모두 지워주는 방식으로 답을 구한다!

Code

C++ 1

#include <vector>
#include <iostream>
using namespace std;

class Solution
{
public:
    int countPrimes(int n)
    {
        // Sieve Of Eratothons
        // idx : 0 to n

        if (n == 0 || n == 1)
            return 0;
        vector<bool> nums(n + 1, true);
        for (int i = 2; i * i <= n; i++)
        {

            if (nums[i])
            {
                for (int j = i * i; j <= n; j += i)
                {
                    nums[j] = false;
                }
            }
        }
        int count = 0;
        for (int i = 2; i < n; i++)
        {
            if (nums[i])
            {
                count++;
            }
        }
        return count;
    }
};

C++ 2

#include <vector>
#include <iostream>
using namespace std;

class Solution
{
public:
    int countPrimes(int n)
    {
        // Sieve Of Eratothons
        // idx : 0 to n

        if (n == 0 || n == 1)
            return 0;
        vector<bool> nums(n + 1, true);
        for (int i = 2; i <= n; i++) 
        {
            if (nums[i])
            {
                for (int j = i + i; j <= n; j += i)
                {
                    nums[j] = false;
                }
            }
        }
        int count = 0;
        for (int i = 2; i < n; i++)
        {
            if (nums[i])
            {
                count++;
            }
        }
        return count;
    }
};