Prime Numbers

Prime numbers are numbers that are greater than 1 and have no divisors other than 1 and itself. They play a significant role in number theory and have various applications in cryptography, algorithms, and mathematical problems.

To determine if a number is prime, we can use the "trial division" approach, which involves checking if the number is divisible by any integer from 2 to the square root of the number. If it is divisible by any of these integers, then it is not prime. Otherwise, it is a prime number.

Let's solve a problem called "Count Primes" which requires us to count the number of prime numbers less than a given non-negative integer n.

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

Here's the Python code to solve the problem:

def countPrimes(n):
    if n <= 2:
        return 0

    # Create a boolean array to mark prime numbers
    is_prime = [True] * n
    is_prime[0] = is_prime[1] = False

    # Loop from 2 to square root of n
    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i]:
            # Mark all multiples of i as non-prime
            for j in range(i * i, n, i):
                is_prime[j] = False

    # Count the number of primes
    count = sum(is_prime)
    return count

# Test the function with the given example
print(countPrimes(10))

The output of the above code will be:

4

The time complexity of this solution is O(n log log n) due to the Sieve of Eratosthenes algorithm used. The space complexity is O(n) since we use a boolean array to mark prime numbers.

In this problem, we used the concept of prime numbers and the Sieve of Eratosthenes algorithm to efficiently count the number of prime numbers less than a given value.