Problem overview
The function countPrimes receives a vector of integers, nums, and returns how many of them are prime. A prime is greater than 1 and divisible only by 1 and itself. 0 and 1 are not prime, and a number that appears several times counts each time.
For [2, 3, 4, 5, 6] the answer is 3, because 2, 3 and 5 are prime. For [0, 1, 9] it is 0. For [7, 10, 7] it is 2: 7 is prime and appears twice, while 10 is 2 times 5.
The work is split in two. The helper isPrime decides about one number, and countPrimes goes over the vector and counts the numbers for which the helper says yes.
Approach: test one number, then count
To test one number n, look for a divisor. If any d from 2 to n - 1 divides n evenly, n has a divisor other than 1 and itself, so it is not prime. If none does, it is prime. Numbers below 2 are rejected first, since the definition requires a prime to be greater than 1.
The counting function then needs nothing more than a counter and a loop. It asks the helper about each number and adds 1 when the answer is true. The helper's own loop runs again for every number, but countPrimes only calls it and doesn't need to know how it works.
Following [7, 10, 7]: the helper tests 7 against 2, 3, 4, 5 and 6, finds no divisor, and says yes. For 10, the very first divisor tried, 2, divides it, so the answer is no. The second 7 is tested again from scratch and counts again. The total is 2.
Step by step
- Reject numbers below 2. In
isPrime, returnfalsewhenn < 2. This covers 0 and 1, and no prime is smaller than 2. - Loop over possible divisors. Start
dat 2 and go up whiled < n. The loop never tries 1 ornitself, which divide everything. - Return
falseon the first divisor. Whenn % d == 0, one divisor is enough. Thereturnleaves both the loop and the function. - Return
trueafter the loop. The loop finished without finding a divisor. - In
countPrimes, createcountset to 0. No prime has been found yet. - Loop over
numswith a range-basedforand anintnamednum. A repeated number is visited once per appearance, which is why it counts each time. - Test with the helper.
isPrime(num)is already abool, so it goes straight into theif. Ontrue, docount++. - Return
countafter the loop. Returning inside the loop would stop after the first number.
The solution in C++
class Solution {
public:
bool isPrime(int n) {
if (n < 2) {
return false;
}
for (int d = 2; d < n; d++) {
if (n % d == 0) {
return false;
}
}
return true;
}
int countPrimes(vector<int> &nums) {
int count = 0;
for (int num : nums) {
if (isPrime(num)) {
count++;
}
}
return count;
}
};
C++ details:
- Boolean conditions.
isPrimereturns abool, soif (isPrime(num))needs no comparison withtrue. - The remainder operator.
n % d == 0meansddividesnexactly. With the lesson's non-negative inputs, the sign rules of%for negative numbers never come up, and negatives would be rejected by the first check anyway. - Early return from a loop. A
returninside aforends the whole function, not only the loop. That is why the finalreturn trueis safe: it is reached only when no divisor returned earlier.
Complexity
For one number n, isPrime does at most n - 2 remainder checks, so O(n) in the worst case. A composite number usually stops early: 100000 returns false at d = 2. A prime has to run the full loop. With values up to 100000, a prime near the top costs about 100000 checks. Over a vector of k numbers the worst case is O(k * M), where M is the largest value. Memory is constant: a few integers.
A faster test, for later
If n has a divisor larger than its square root, it also has a matching one smaller than the square root, so the loop can stop at d * d <= n. That turns O(n) into O(sqrt(n)) per number. Counting the primes from 0 to 100000 gives 9592 with both versions. This lesson keeps the simpler loop, which is fast enough for its limits and makes the definition visible in the code.
Edge cases and common mistakes
- 0 and 1. Without the first check, the loop would not run for either, and the function would return
true. Then < 2test prevents that. - 2. For
n = 2the loop conditiond < nis false from the start, so the function returnstrue, which is right: 2 is the smallest prime. - Loop bound too large. With
d <= n, every number would divide itself and nothing would be prime. - Counting distinct primes. The task counts every appearance, so
[2, 2, 2]gives 3. - Returning inside the counting loop. The function would stop after the first number.
Testing
[2, 3, 4, 5, 6]gives 3.[0, 1, 9]gives 0.[7, 10, 7]gives 2.[2, 2, 2]gives 3.isPrime(2)is true,isPrime(1)andisPrime(0)are false,isPrime(99991)is true andisPrime(100000)is false.
