Sponsored
Sponsored
The Sieve of Eratosthenes is a classic algorithm to find all prime numbers up to a given limit. It efficiently marks non-prime numbers in a boolean array, allowing us to count the prime numbers left unmarked.
It operates by marking the multiples of each prime starting from 2, the smallest prime. This optimization significantly reduces the number of operations needed compared to checking each number individually.
Time Complexity: O(n log log n)
Space Complexity: O(n)
1def count_primes(n):
2 if n <= 2:
3 return 0
4 is_prime = [True] * n
5 is_prime[0] = is_prime[1] = False
6 for i in range(2, int(n**0.5) + 1):
7 if is_prime[i]:
8 for j in range(i * i, n, i):
9 is_prime[j] = False
10 return sum(is_prime)
11
12print(count_primes(10)) # Output: 4
13Python's implementation relies on list comprehension and the sum function to efficiently count prime numbers. The Sieve of Eratosthenes is applied similarly to other language solutions, demonstrating Python's elegant handling of list operations.
A more basic approach to this problem is to check each number individually for primality. This involves testing each number for factors up to its square root. While less efficient than the sieve, it provides an instructive example of brute force in algorithm design.
Time Complexity: O(n√n)
Space Complexity: O(1)
1public
This Java implementation closely mirrors the C/C++ naive primality test. The isPrime method checks each number's factors up to the square root to confirm primality. This is run iteratively up to n.