Prime Numbers

What is a Prime Number?

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Method 1: Naive Approach

class Solution
{
public:
    bool isPrime(int n)
    {
        if (n <= 1)
            return false;
        for (int i = 2; i < n; i++)
        {
            if (n % i == 0)
                return false;
        }
        return true;
    }

    int countPrimes(int n)
    {
        int c = 0;
        for (int i = 2; i < n; ++i)
        {
            if (isPrime(i))
                ++c;
        }
        return c;
    }
};

Time Complexity: O(n²) Space Complexity: O(1)

Method 2: Optimized Check

class Solution
{
public:
    bool isPrime(int n)
    {
        if (n <= 1)
            return false;
        for (int i = 2; i * i <= n; i++)
        {
            if (n % i == 0)
                return false;
        }
        return true;
    }

    int countPrimes(int n)
    {
        int c = 0;
        for (int i = 2; i < n; ++i)
        {
            if (isPrime(i))
                ++c;
        }
        return c;
    }
};

Time Complexity: O(n√n) Space Complexity: O(1)

Counting Primes (LeetCode 204)

Method Time Complexity Space Complexity Approach
Naive O(n²) O(1) Check each number individually
Optimized O(n√n) O(1) Check till √n for each number
Sieve O(n log (log n)) O(n) Mark multiples as composite

Best Approach: Sieve of Eratosthenes

class Solution
{
public:
    int countPrimes(int n)
    {
        vector<bool> prime(n + 1, true);
        prime[0] = prime[1] = false;
        int ans = 0;

        for (int i = 2; i < n; i++)
        {
            if (prime[i])
            {
                ++ans;

                int j = i * i;
                while (j < n)
                {
                    prime[j] = false;
                    j += i;
                }
            }
        }
        return ans;
    }
};

GCD / HCF

Both mean the same thing: the largest number that divides two (or more) numbers exactly.

Euclidean Algorithm for GCD

Formula: gcd(a, b) = gcd(a − b,b) when a>b