Dare2Solve
Given an integer n
, the task is to return the number of prime numbers that are strictly less than n
. Prime numbers are numbers greater than 1 that have no divisors other than 1 and themselves.
The problem can be efficiently solved using the Sieve of Eratosthenes algorithm, which systematically marks the multiples of each prime number starting from 2. By the end of this process, all numbers that are still unmarked are prime. The key idea is to minimize unnecessary calculations and prevent overflow by handling large numbers carefully.
Initialization:
seen
of size n
, initialized to false
. This array will keep track of which numbers have been marked as non-prime.ans
to zero, which will store the number of primes found.Outer Loop (Iterate Through Potential Primes):
2
to n-1
.seen[num] == false
), it is a prime, so increment ans
.num * num
does not exceed n
to avoid overflow.Inner Loop (Mark Multiples):
num
, start marking multiples of num
beginning from num * num
.seen[mult] = true
for each multiple to indicate that it is not a prime.Return Result:
ans
, which represents the count of prime numbers less than n
.O(n log log n)
, which is the time complexity of the Sieve of Eratosthenes. The outer loop runs in O(n)
time, but marking multiples (inner loop) for each prime runs in O(log log n)
time on average.
O(n)
, as we use an array of size n
to keep track of whether each number is prime.
class Solution {
public:
int countPrimes(int n) {
if (n < 2) return 0;
vector<bool> seen(n, false);
int ans = 0;
for (int num = 2; num < n; num++) {
if (seen[num]) continue;
ans++;
if (num > sqrt(n)) continue; // Prevent overflow
for (int mult = num * num; mult < n; mult += num) {
seen[mult] = true;
}
}
return ans;
}
};
class Solution:
def countPrimes(self, n: int) -> int:
if n < 2:
return 0
seen = [False] * n
ans = 0
for num in range(2, n):
if seen[num]:
continue
ans += 1
for mult in range(num * num, n, num):
seen[mult] = True
return ans
class Solution {
public int countPrimes(int n) {
if (n < 2) return 0;
boolean[] seen = new boolean[n];
int ans = 0;
for (int num = 2; num < n; num++) {
if (seen[num]) continue;
ans++;
if ((long)num * num >= n) continue; // Prevent overflow
for (int mult = num * num; mult < n; mult += num) {
seen[mult] = true;
}
}
return ans;
}
}
/**
* @param {number} n
* @return {number}
*/
var countPrimes = function(n) {
let seen = new Uint8Array(n), ans = 0
for (let num = 2; num < n; num++) {
if (seen[num]) continue
ans++
for (let mult = num * num; mult < n; mult += num)
seen[mult] = 1
}
return ans
};