What is the time complexity of Count Primes?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Count Primes?

This problem uses Array, Math, Enumeration, Number Theory. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Count Primes?

Insight 1: The Sieve of Eratosthenes is an efficient algorithm for finding all prime numbers up to a specified integer. Insight 2: We only need to iterate up to the square root of `n` when marking composite numbers. This is because if a number `n` is composite, it must have a factor less than or equal to its square root.

Which companies ask LeetCode 204. Count Primes in interviews?

This problem is frequently asked at Accenture, Cognizant, Intel, Nokia, Salesforce and 4 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Count Primes - LeetCode 204 Solution

Q: How to solve Count Primes?

The solution uses the Sieve of Eratosthenes to efficiently find all prime numbers less than `n`. We create a boolean array `is_prime` of size `n`, where `is_prime[i]` represents whether the number `i` is prime. Initially, we assume all numbers are prime (except 0 and 1). Then, we iterate through the array, starting from 2. If a number `p` is marked as prime, we mark all its multiples (starting from p*p) as composite (not prime). After this process, the number of `True` values in the `is_prime` array represents the number of primes less than `n`.

Count Primes - Complete Solution Guide

Count Primes is LeetCode problem 204, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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

Detailed Explanation

The problem asks us to count the number of prime numbers strictly less than a given integer `n`. A prime number is a natural number greater than 1 that is not a product of two smaller natural numbers. In other words, a prime number has only two distinct positive divisors: 1 and itself. For example, the prime numbers less than 10 are 2, 3, 5, and 7. The input is a non-negative integer `n`, and the output is the number of primes less than `n`. The constraint is that `0 <= n <= 5 * 10^6`.

Solution Approach

The solution uses the Sieve of Eratosthenes to efficiently find all prime numbers less than `n`. We create a boolean array `is_prime` of size `n`, where `is_prime[i]` represents whether the number `i` is prime. Initially, we assume all numbers are prime (except 0 and 1). Then, we iterate through the array, starting from 2. If a number `p` is marked as prime, we mark all its multiples (starting from p*p) as composite (not prime). After this process, the number of `True` values in the `is_prime` array represents the number of primes less than `n`.

Step-by-Step Algorithm

Step 1: Handle the base cases where n <= 2. In these cases, there are no prime numbers less than n, so return 0.
Step 2: Create a boolean array `is_prime` of size `n`, initialized to `True` for all indices. This array will be used to mark prime numbers.
Step 3: Mark `is_prime[0]` and `is_prime[1]` as `False`, since 0 and 1 are not prime.
Step 4: Iterate from `p = 2` to the square root of `n`. If `is_prime[p]` is `True` (meaning `p` is prime), then mark all multiples of `p` starting from `p*p` as `False` (composite). The multiples are marked with a step of `p`.
Step 5: Count the number of `True` values in the `is_prime` array. This count represents the number of prime numbers less than `n`.
Step 6: Return the count of prime numbers.

Key Insights

Insight 1: The Sieve of Eratosthenes is an efficient algorithm for finding all prime numbers up to a specified integer.
Insight 2: We only need to iterate up to the square root of `n` when marking composite numbers. This is because if a number `n` is composite, it must have a factor less than or equal to its square root.
Insight 3: The space complexity can become an issue for large n, but the problem constraint limits the size of n.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Array, Math, Enumeration, Number Theory.

Companies

Asked at: Accenture, Cognizant, Intel, Nokia, Salesforce, Tech Mahindra, Walmart Labs, Wipro, tcs.

Count Primes | LeetCode 204

Medium

Array Math Enumeration Number Theory

Time: O(n)Space: O(n)

Solution Code

Available in:

class Solution {
    public int countPrimes(int n) {
        if (n <= 2) {
            return 0;
        }
        
        boolean[] is_prime = new boolean[n];
        for (int i = 0; i < n; i++) {
            is_prime[i] = true;
        }
        is_prime[0] = is_prime[1] = false;
        
        for (int p = 2; p <= Math.sqrt(n); p++) {
            if (is_prime[p]) {
                for (int i = p * p; i < n; i += p) {
                    is_prime[i] = false;
                }
            }
        }
        
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (is_prime[i]) {
                count++;
            }
        }
        
        return count;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 204: Count Primes - Detailed explanation and solution approaches.

Topics

Array Math Enumeration Number Theory

Companies

AccentureCognizantIntelNokiaSalesforceTech MahindraWalmart LabsWipro

Stats

Difficulty:Medium

Languages:4

Companies:9

Problem #:204

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

6 steps

1
Step 1: Handle the base cases where n <= 2. In these cases, there are no prime numbers less than n, so return 0.
2
Step 2: Create a boolean array `is_prime` of size `n`, initialized to `True` for all indices. This array will be used to mark prime numbers.
3
Step 3: Mark `is_prime[0]` and `is_prime[1]` as `False`, since 0 and 1 are not prime.
4
Step 4: Iterate from `p = 2` to the square root of `n`. If `is_prime[p]` is `True` (meaning `p` is prime), then mark all multiples of `p` starting from `p*p` as `False` (composite). The multiples are marked with a step of `p`.
5
Step 5: Count the number of `True` values in the `is_prime` array. This count represents the number of prime numbers less than `n`.
6
Step 6: Return the count of prime numbers.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is derived from the Sieve of Eratosthenes algorithm. The outer loop runs for `sqrt(n)` iterations. The inner loop's contribution can be more accurately analyzed. Each composite number is marked by its smallest prime factor. The sum of reciprocals of primes diverges very slowly. Summation of 1/p for primes p <= n can be approximated by log(log(n)). Marking multiples contributes `n/p` in the inner loop. Summing up the work across primes gives n * (sum 1/p for p <= sqrt(n)), resulting in O(n log log n). The space complexity arises because we create a boolean array of size n.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Trial Division

Iterate through numbers from 2 to n-1, and for each number, check if it's prime by dividing it by all numbers from 2 to its square root. If none of the numbers divide it evenly, then it's prime.

Time: O(n * sqrt(n))Space: O(1)

Trade-offs: Trial division is much simpler to implement but significantly less efficient than the Sieve of Eratosthenes for larger values of `n`. It uses constant extra space, making it suitable if memory is extremely limited and `n` is small.

✨

Key Insights

1Insight 1: The Sieve of Eratosthenes is an efficient algorithm for finding all prime numbers up to a specified integer.
2Insight 2: We only need to iterate up to the square root of `n` when marking composite numbers. This is because if a number `n` is composite, it must have a factor less than or equal to its square root.
3Insight 3: The space complexity can become an issue for large n, but the problem constraint limits the size of n.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Edge Cases

Edge case 1: `n = 0`. The solution correctly returns 0 because there are no prime numbers less than 0.
Edge case 2: `n = 1`. The solution correctly returns 0 because there are no prime numbers less than 1.
Edge case 3: `n = 2`. The solution correctly returns 0 because the only prime number less than 2 is none.
Edge case 4: Large values of `n` close to the constraint limit (5 * 10^6). The solution handles this correctly due to the boolean array's size and the algorithm's efficiency. Memory allocation is not an issue within the stated constraints.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not handling the base cases of `n <= 2` correctly, resulting in incorrect counts or errors.

✗Common mistake 2: Iterating up to `n` instead of `sqrt(n)` in the outer loop when marking composites. This leads to unnecessary computations and doesn't improve the result.

✗Common mistake 3: Starting the inner loop from `p` instead of `p*p`. This can result in marking numbers as composite multiple times (e.g., marking `2*p` and `p*2` both as composite), although it doesn't affect the final count, but affects the time.

✗Common mistake 4: Forgetting to exclude 0 and 1 as prime numbers.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Cryptography. Prime numbers are fundamental to many cryptographic algorithms, such as RSA. Efficiently finding prime numbers is crucial in generating keys and ensuring secure communication.

🏦Real-world scenario 2: Hashing. Prime numbers are often used in hash functions to minimize collisions and distribute data evenly across a hash table.

🎮Real-world scenario 3: Data compression. Some data compression algorithms utilize prime numbers to optimize the compression process.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 25, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 13

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 6

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Count Primes"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether math techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?