Count Primes (Sieve of Eratosthenes)

▶

Steps

setup

Check if n ≤ 2

The algorithm first checks if the input n is less than or equal to 2. Since n=10, it proceeds to initialize the sieve.

💡 This step handles trivial cases quickly, avoiding unnecessary computation for very small inputs.

Line:

if n <= 2:
    return 0

💡 The algorithm only runs the sieve for inputs greater than 2, as there are no primes less than 2.

setup

Initialize is_prime array for odd numbers

Create a boolean array is_prime of size n//2 = 5, representing odd numbers 3,5,7,9,11 (index 0 to 4). All values are initially True.

💡 Only odd numbers are tracked to save space and time, since even numbers >2 are not prime.

Line:

is_prime = [True] * (n // 2)

💡 The array length 5 corresponds to odd numbers starting at 3: index 0 → 3, index 1 → 5, etc.

setup

Mark 1 as not prime

Set is_prime[0] = False because 1 is not a prime number. Index 0 corresponds to number 1 (2*0+1=1).

💡 Although the array is meant for odd numbers starting at 3, index 0 corresponds to 1, which is not prime and must be excluded.

Line:

is_prime[0] = False  # 1 is not prime

💡 This step ensures the algorithm does not mistakenly count 1 as prime.

traverse

Start outer loop with i=3

Set i=3, the first odd candidate prime to check. The loop will run while i ≤ sqrt(n) (i ≤ 3).

💡 We only check odd numbers starting from 3 up to sqrt(n) to mark their multiples.

Line:

for i in range(3, int(n**0.5) + 1, 2):

💡 The loop will run for i=3 only since sqrt(10) ≈ 3.16.

compare

Check if is_prime[i//2] is True for i=3

Check if is_prime[3//2] = is_prime[1] is True. Since it is True, proceed to mark multiples of 3.

💡 Only if the current candidate is still marked prime do we mark its multiples.

Line:

if is_prime[i // 2]:

💡 This confirms 3 is prime and its multiples need to be marked.

prune

Start inner loop to mark multiples of 3

Begin marking multiples of 3 starting from 3*3=9, stepping by 2*3=6, as non-prime in the array.

💡 Marking starts at i*i because smaller multiples were marked by smaller primes.

Line:

for j in range(i * i, n, 2 * i):

💡 Only odd multiples of 3 are marked, skipping even multiples.

prune

Mark multiple j=9 as non-prime

Mark is_prime[9//2] = is_prime[4] as False because 9 is a multiple of 3 and not prime.

💡 Marking multiples as False removes them from prime candidates.

Line:

is_prime[j // 2] = False

💡 Index 4 corresponds to number 9, now marked non-prime.

prune

Increment j beyond n, end inner loop

Next j would be 9 + 6 = 15, which is ≥ n=10, so inner loop ends.

💡 No more multiples of 3 less than n to mark.

Line:

for j in range(i * i, n, 2 * i):

💡 All relevant multiples of 3 have been marked.

traverse

Increment i to 5, check loop condition

Increment i by 2 to 5. Check if i ≤ sqrt(n) (5 ≤ 3). Condition false, so outer loop ends.

💡 Only odd numbers up to sqrt(n) are checked as prime candidates.

Line:

for i in range(3, int(n**0.5) + 1, 2):

💡 No more prime candidates to check for marking multiples.

reconstruct

Count primes and return result

Count primes by adding 1 for prime 2 plus the number of True values in is_prime. Here, True count is 3, total 4.

💡 Prime 2 is counted separately since the array tracks only odd numbers.

Line:

return 1 + sum(is_prime)  # add prime 2

💡 The final count of primes less than 10 is 4: 2, 3, 5, and 7.

def countPrimes(n):
    # STEP 1
    if n <= 2:
        return 0
    # STEP 2
    is_prime = [True] * (n // 2)
    # STEP 3
    is_prime[0] = False  # 1 is not prime
    # STEP 4
    for i in range(3, int(n**0.5) + 1, 2):
        # STEP 5
        if is_prime[i // 2]:
            # STEP 6
            for j in range(i * i, n, 2 * i):
                # STEP 7
                is_prime[j // 2] = False
    # STEP 10
    return 1 + sum(is_prime)  # add prime 2

if __name__ == '__main__':
    print(countPrimes(10))  # Output: 4

📊

Count Primes (Sieve of Eratosthenes) - Watch the Algorithm Execute, Step by Step

Watching each marking of multiples and pointer movement reveals how the sieve efficiently eliminates non-primes without checking every number.

compare

fill_row

0

1

2

3

4

insert

0

1

2

3

4

move_right

0

i

1

2

3

4

compare

0

i

1

2

3

4

move_right

0

i

1

2

3

j

4

insert

0

i

1

2

3

j

4

move_right

0

i

1

2

3

4

move_right

0

1

2

3

4

record

0

1

2

3

4

Result: 4

Key Takeaways

✓ The sieve efficiently skips even numbers by representing only odds, reducing memory and computation.

This optimization is not obvious from code alone but is clear when seeing the array represent only odd numbers.

✓ Marking multiples starts at i*i because smaller multiples are already handled by smaller primes.

This insight explains why the inner loop starts at i*i, which can be confusing without visualization.

✓ The final count adds 1 for prime 2 separately since the array excludes even numbers.

Understanding this separate counting clarifies why the algorithm returns 1 + sum(is_prime).

Practice

1. You need to find the smallest positive number that is divisible by two given integers, and also find the greatest integer that divides both. Which approach guarantees the most efficient and reliable solution for this problem?

easy

A. Use a brute force search checking multiples and divisors until the answer is found.

B. Use a greedy algorithm that picks the largest divisor first and tries to build the LCM.

C. Apply the Euclidean algorithm iteratively to find GCD, then compute LCM using the GCD.

D. Use dynamic programming to store intermediate divisors and multiples for both numbers.

Solution

1. Step 1: Understand the problem requirements

   The problem requires finding the greatest common divisor (GCD) and least common multiple (LCM) of two integers efficiently.

2. Step 2: Evaluate approaches

   Brute force is inefficient for large inputs. Dynamic programming and greedy approaches do not naturally fit this problem. The Euclidean algorithm efficiently computes GCD in O(log(min(a,b))) time, and LCM can be derived from GCD.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Euclidean algorithm is the standard optimal method for GCD and LCM [OK]

Hint: Euclidean algorithm efficiently finds GCD and LCM [OK]

Common Mistakes:

• Thinking brute force is efficient enough
• Confusing greedy with Euclidean algorithm

2. You are given a list of points on a 2D plane. Your task is to find the rectangle with the minimum area such that all four corners are points from the list. Which approach guarantees finding the optimal solution efficiently?

easy

A. Use a hash set to store points and check pairs of points as diagonals to find rectangles.

B. Use dynamic programming to build rectangles from smaller sub-rectangles.

C. Use a greedy approach by sorting points and selecting closest pairs to form rectangles.

D. Use a brute force approach checking all quadruples of points to find rectangles.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding rectangles formed by points with minimum area, which involves checking pairs of points as potential diagonals.

2. Step 2: Evaluate approaches

   Brute force (checking all quadruples) is correct but inefficient (O(n^4)). Greedy and DP approaches do not guarantee correctness or efficiency here. Using a hash set to check existence of complementary points for diagonals is both correct and efficient (O(n^2)).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Hash set + diagonal pairs -> optimal and correct [OK]

Hint: Hash set + diagonal pairs is key [OK]

Common Mistakes:

• Thinking greedy or DP solves this efficiently
• Using brute force without pruning

3. What is the time complexity of the iterative Euclidean algorithm used to compute the GCD of two integers a and b, where a ≥ b > 0?

medium

A. O(min(a, b))

B. O(a + b)

C. O(1)

D. O(log(min(a, b)))

Solution

1. Step 1: Identify the Euclidean algorithm's iteration count

   The Euclidean algorithm reduces the problem size roughly by at least half every two iterations, leading to logarithmic steps in the smaller number.

2. Step 2: Conclude time complexity

   Therefore, the time complexity is O(log(min(a, b))). Linear or constant time complexities are incorrect.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Euclidean algorithm runs in logarithmic time relative to smaller input [OK]

Hint: Euclidean algorithm halves problem size quickly [OK]

Common Mistakes:

• Assuming linear time proportional to min(a,b)
• Confusing with brute force complexity

4. Suppose the Excel column titles can now include lowercase letters (a-z) in addition to uppercase (A-Z), where 'a' corresponds to 1 and 'z' to 26, independent of uppercase letters. How should the algorithm be modified to correctly convert such titles to numbers?

hard

A. Convert all letters to uppercase and use existing logic

B. Treat uppercase letters as base-26 digits and lowercase letters as separate base-26 digits, then sum

C. Use a combined mapping where 'A'-'Z' and 'a'-'z' both map to 1-26, then apply base-26 logic

D. Map uppercase and lowercase letters separately to 1-26 and multiply by 52 instead of 26

Solution

1. Step 1: Understand the new character set

   Now there are 52 possible characters (A-Z and a-z), each mapping to 1-26 independently.

2. Step 2: Adjust base and mapping accordingly

   Since there are 52 distinct characters, the base must be 52, and mapping must distinguish uppercase and lowercase letters.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Base must match character set size; 26 is insufficient for mixed case [OK]

Hint: Base equals number of distinct characters [OK]

Common Mistakes:

• Ignoring case difference
• Using base 26 for 52 chars
• Mapping lowercase to same as uppercase

5. Suppose the problem is modified so that points can have negative coordinates and the input size is very large. Which modification to the optimal approach is necessary to maintain efficiency and correctness?

hard

A. Use a hash set as before, since it supports negative coordinates and lookups remain O(1).

B. Replace the hash set with a balanced binary search tree to handle negative coordinates efficiently.

C. Sort points by coordinates and use two pointers to find rectangles, avoiding hash sets.

D. Switch to brute force checking all quadruples since negative coordinates break the hash set approach.

Solution

1. Step 1: Consider data structure requirements

   Hash sets in Python support negative integers as keys with O(1) average lookup time.

2. Step 2: Evaluate alternatives

   Replacing with balanced trees adds unnecessary overhead; sorting and two pointers do not guarantee rectangle detection efficiently; brute force is too slow.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Hash set handles negative coords efficiently -> no change needed [OK]

Hint: Hash sets handle negative keys naturally [OK]

Common Mistakes:

• Thinking hash sets can't handle negative keys
• Switching to slower data structures unnecessarily