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)
1#include <stdio.h>
2#include <stdbool.h>
3
4int countPrimes(int n) {
5 if (n <= 2) return 0;
6 bool isPrime[n];
7 for (int i = 0; i < n; i++) isPrime[i] = true;
8 isPrime[0] = isPrime[1] = false;
9 for (int i = 2; i * i < n; i++) {
10 if (isPrime[i]) {
11 for (int j = i * i; j < n; j += i) {
12 isPrime[j] = false;
13 }
14 }
15 }
16 int count = 0;
17 for (int i = 2; i < n; i++) {
18 if (isPrime[i]) count++;
19 }
20 return count;
21}
22
23int main() {
24 printf("%d\n", countPrimes(10)); // Output: 4
25 return 0;
26}
27This implementation uses a boolean array to keep track of prime numbers. We initialize the array assuming all numbers are prime, then use the Sieve of Eratosthenes method to mark non-prime numbers. Finally, we count the number of prime numbers remaining unmarked up to n.
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)
1def is_prime(
In Python, the naive solution applies a similar is_prime function, utilizing trial division to assess the primality of each number less than n. Despite being less efficient, it demonstrates a straightforward necessity for optimization with larger inputs.