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)
1using System;
2
3public class Solution {
4 public int CountPrimes(int n) {
5 if (n <= 2) return 0;
6 bool[] isPrime = new bool[n];
7 Array.Fill(isPrime, 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 foreach (bool prime in isPrime) {
18 if (prime) count++;
19 }
20 return count;
21 }
22
23 public static void Main() {
24 Solution sol = new Solution();
25 Console.WriteLine(sol.CountPrimes(10)); // Output: 4
26 }
27}
28This C# implementation effectively applies the Sieve of Eratosthenes with boolean arrays. Using Array.Fill ensures efficient array initialization, and the algorithm proceeds to mark non-prime numbers as expected.
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)
1#include
This solution implements a naive primality test, evaluating the primality of each number up to n. For each number, divisibility is tested up to the square root to determine if it is prime. Though simple, this method is not optimized for large input values.