Jobs

Interviews

Discussions

Count Primes

Medium

Intel

3 views

Topics:

ArraysTwo Pointers

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⁶

Try coding it in LeetCode

Count Primes

Medium

Intel

3 views

Topics:

ArraysTwo Pointers

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⁶

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the upper bound for the input integer 'n'? Should I be concerned about potential integer overflow issues?
Is 'n' inclusive or exclusive when determining the range of numbers to consider for primality (i.e., should I count primes less than or equal to n-1)?
What should I return if 'n' is zero, negative, or one?
Are there any specific memory constraints I should be aware of, given the potential range of 'n'?
Can I assume 'n' is always an integer?

Brute Force Solution

Approach

To count primes using a brute force method, we essentially check every number one by one to see if it is a prime number. We do this by testing if any smaller number can perfectly divide it. If no smaller number divides it, we know that number is prime and increment our count.

Here's how the algorithm would work step-by-step:

Start counting from the first prime number, which is 2.
Consider each number one after another up to the target number.
For each number, check if any number smaller than it (but greater than 1) divides it evenly (without any remainder).
If you find a number that divides it evenly, then the number you're checking is not a prime; move on to the next number.
If you go through all the smaller numbers and none of them divide it evenly, then the number you're checking is a prime; increment the prime count.
Keep repeating steps 3-5 until you've checked every number up to your target number.
The final count will be the total number of prime numbers found.

Code Implementation

def count_primes_brute_force(target_number):
    number_of_primes = 0
    
    for number in range(2, target_number):
        is_prime = True
        
        # Iterate from 2 up to the number to check divisibility
        for potential_divisor in range(2, number):

            # Check if the number is divisible by the potential divisor
            if number % potential_divisor == 0:
                is_prime = False
                break

        # If, after checking all potential divisors, is_prime is still True,
        # then the number is prime, increment the counter.
        if is_prime:

            number_of_primes += 1

    return number_of_primes

Big(O) Analysis

Time Complexity

O(n²) – The outer loop iterates from 2 up to n (exclusive). For each number in the outer loop, the inner loop checks for divisibility from 2 up to that number (exclusive). Therefore, for each number n, we perform up to n-2 division operations. Thus, the total number of operations is proportional to the sum of numbers from 2 to n-2, which approximates to n * n/2. Simplifying this, the time complexity is O(n²).

Space Complexity

O(1) – The provided algorithm checks each number from 2 up to N for primality by iterating through numbers smaller than it. It only uses a few integer variables: one to track the current number being checked, another to iterate through potential divisors, and one to count the primes. No additional data structures like arrays or hash maps are created, meaning the auxiliary space used does not depend on the input N and remains constant. Therefore, the space complexity is O(1).

Optimal Solution

Approach

Finding prime numbers one by one can take a long time. Instead, we'll use a clever approach to quickly identify all non-prime numbers, leaving us with the primes. This is like finding the bad apples in a basket to easily see which ones are good.

Here's how the algorithm would work step-by-step:

Start by assuming all numbers are prime, like having a list of all good apples to begin with.
Begin with the first prime number, which is 2. Go through the list and mark all multiples of 2 as not prime (or bad apples).
Move to the next unmarked number. It's a prime! (because if it wasn't, it would already be marked). Now mark all of *its* multiples as not prime.
Repeat this process: find the next unmarked number, mark its multiples. Stop when you've checked all the necessary numbers. You only need to go up to the square root of the number you're given.
Finally, count how many numbers are still marked as prime. These are your prime numbers.

Code Implementation

def count_primes(number): 
    if number <= 2:
        return 0

    is_prime = [True] * number
    is_prime[0] = is_prime[1] = False

    # Iterate up to the square root for optimization.
    for i in range(2, int(number**0.5) + 1): 
        if is_prime[i]:

            # Start marking from i*i since smaller multiples are already marked.
            for multiple in range(i*i, number, i):
                is_prime[multiple] = False

    # Count the remaining primes.
    prime_count = sum(is_prime)
    return prime_count

Big(O) Analysis

Time Complexity

O(n log log n) – The algorithm iterates up to the square root of n. For each number i in that range, it marks multiples of i as non-prime. The inner loop, marking multiples, isn't executed n times for each i. The number of multiples decreases as i increases, approximating a harmonic series. Summing the work done, we get approximately n/2 + n/3 + n/5 + ... which is related to the harmonic series and approximates to n log log n, thus the overall time complexity is O(n log log n).

Space Complexity

O(N) – The algorithm uses a boolean array, let's call it 'isPrime', of size N to keep track of whether each number is prime or not. Initially, all elements in 'isPrime' are marked as true, representing that all numbers are assumed to be prime. This array is the dominant factor in the auxiliary space used. Therefore, the space complexity is directly proportional to the input N, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Input n is 0	Return 0 immediately, as there are no primes less than 0.
Input n is 1	Return 0 immediately, as there are no primes less than 1.
Input n is 2	Return 0 immediately, as 2 is not less than 2.
Input n is a large number close to the maximum integer value	Ensure the Sieve of Eratosthenes algorithm implementation does not cause integer overflow when calculating indices or allocating memory for the boolean array.
Negative input for n	Treat negative inputs as 0 and return 0, as the problem specifies non-negative numbers.
Input n is a prime number, such as 7	The algorithm should correctly count primes strictly less than n, excluding n itself.
The input n is a perfect square, such as 9	The algorithm should not double count primes when checking divisibility, this is inherent in the Sieve of Eratosthenes.
Input n results in a very large boolean array (memory constraints)	Consider memory usage optimization if n is excessively large; an alternative approach might be needed if memory becomes a bottleneck.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the upper bound for the input integer 'n'? Should I be concerned about potential integer overflow issues?
Is 'n' inclusive or exclusive when determining the range of numbers to consider for primality (i.e., should I count primes less than or equal to n-1)?
What should I return if 'n' is zero, negative, or one?
Are there any specific memory constraints I should be aware of, given the potential range of 'n'?
Can I assume 'n' is always an integer?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start counting from the first prime number, which is 2.
Consider each number one after another up to the target number.
For each number, check if any number smaller than it (but greater than 1) divides it evenly (without any remainder).
If you find a number that divides it evenly, then the number you're checking is not a prime; move on to the next number.
If you go through all the smaller numbers and none of them divide it evenly, then the number you're checking is a prime; increment the prime count.
Keep repeating steps 3-5 until you've checked every number up to your target number.
The final count will be the total number of prime numbers found.

Code Implementation

def count_primes_brute_force(target_number):
    number_of_primes = 0
    
    for number in range(2, target_number):
        is_prime = True
        
        # Iterate from 2 up to the number to check divisibility
        for potential_divisor in range(2, number):

            # Check if the number is divisible by the potential divisor
            if number % potential_divisor == 0:
                is_prime = False
                break

        # If, after checking all potential divisors, is_prime is still True,
        # then the number is prime, increment the counter.
        if is_prime:

            number_of_primes += 1

    return number_of_primes

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start by assuming all numbers are prime, like having a list of all good apples to begin with.
Begin with the first prime number, which is 2. Go through the list and mark all multiples of 2 as not prime (or bad apples).
Move to the next unmarked number. It's a prime! (because if it wasn't, it would already be marked). Now mark all of *its* multiples as not prime.
Repeat this process: find the next unmarked number, mark its multiples. Stop when you've checked all the necessary numbers. You only need to go up to the square root of the number you're given.
Finally, count how many numbers are still marked as prime. These are your prime numbers.

Code Implementation

def count_primes(number): 
    if number <= 2:
        return 0

    is_prime = [True] * number
    is_prime[0] = is_prime[1] = False

    # Iterate up to the square root for optimization.
    for i in range(2, int(number**0.5) + 1): 
        if is_prime[i]:

            # Start marking from i*i since smaller multiples are already marked.
            for multiple in range(i*i, number, i):
                is_prime[multiple] = False

    # Count the remaining primes.
    prime_count = sum(is_prime)
    return prime_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input n is 0	Return 0 immediately, as there are no primes less than 0.
Input n is 1	Return 0 immediately, as there are no primes less than 1.
Input n is 2	Return 0 immediately, as 2 is not less than 2.
Input n is a large number close to the maximum integer value	Ensure the Sieve of Eratosthenes algorithm implementation does not cause integer overflow when calculating indices or allocating memory for the boolean array.
Negative input for n	Treat negative inputs as 0 and return 0, as the problem specifies non-negative numbers.
Input n is a prime number, such as 7	The algorithm should correctly count primes strictly less than n, excluding n itself.
The input n is a perfect square, such as 9	The algorithm should not double count primes when checking divisibility, this is inherent in the Sieve of Eratosthenes.
Input n results in a very large boolean array (memory constraints)	Consider memory usage optimization if n is excessively large; an alternative approach might be needed if memory becomes a bottleneck.