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 <iostream>
2#include <vector>
3
4int countPrimes(int n) {
5 if (n <= 2) return 0;
6 std::vector<bool> isPrime(n, true);
7 isPrime[0] = isPrime[1] = false;
8 for (int i = 2; i * i < n; i++) {
9 if (isPrime[i]) {
10 for (int j = i * i; j < n; j += i) {
11 isPrime[j] = false;
12 }
13 }
14 }
15 return std::count(isPrime.begin(), isPrime.end(), true);
16}
17
18int main() {
19 std::cout << countPrimes(10) << std::endl; // Output: 4
20 return 0;
21}
22The C++ solution also utilizes the Sieve of Eratosthenes. A std::vector of boolean values represents whether each number less than n is prime, initially assuming all numbers are prime. The algorithm proceeds as described above to mark non-prime numbers.
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)
1using System;
2
public class Solution {
public bool IsPrime(int n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
for (int i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) return false;
}
return true;
}
public int CountPrimes(int n) {
int count = 0;
for (int i = 2; i < n; i++) {
if (IsPrime(i)) count++;
}
return count;
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.CountPrimes(10)); // Output: 4
}
}
The C# version uses a similar naive strategy by checking divisibility up to the square root for each number. This method entails iterating through numbers sequentially and assessing their factors.