Problem overview
Given an array of integers nums, return how many of them are prime. A prime is greater than 1 and divisible only by 1 and itself: 2, 3, 5, 7, 11 and so on. 0 and 1 are not prime. A number that appears several times counts every time.
The work is split in two functions. The helper isPrime(n) answers true or false for one number. The method countPrimes(nums) goes over the array and counts the numbers for which the helper says true.
For [2, 3, 4, 5, 6] the answer is 3 (2, 3 and 5). For [0, 1, 9] it is 0, because 9 = 3 × 3. For [7, 10, 7] it is 2, since 7 is prime and counts twice.
Approach
To decide whether n is prime, look for a divisor between 2 and n - 1. One divisor is enough to prove that n is not prime, so the function can return false at once. If the loop ends without finding one, n is prime. Numbers below 2 are handled first, because they have no divisors in that range and would otherwise be reported prime.
Counting is then an ordinary loop: a counter starts at 0, and each number for which isPrime returns true adds 1. Each function has one loop, and the helper's loop runs again for every number the other loop visits.
Trying every candidate up to n - 1 is the simplest correct approach, and it is fast enough for the lesson's limit of 100000 on each value. Stopping at the square root of n would be faster, but this lesson keeps to the plain version.
The square-root shortcut works because divisors come in pairs: if n = p × q, then one of p and q is at most the square root of n. For 97 that means testing only 2 to 9. A composite number such as 36 shows the pairs: 2 × 18, 3 × 12, 4 × 9 and 6 × 6. The lesson's simpler loop finds the same answers, only with more tests.
Step by step
- Reject numbers below 2. In
isPrime,if (n < 2)returnsfalse. This covers 0 and 1. - Write the divisor loop.
dstarts at 2 and goes up whiled < n, so it tries every number from 2 ton - 1. - Test for a divisor. If
n % d == 0, the remainder is zero andddividesnevenly. Returnfalse: the return ends both the loop and the function. - Return
trueafter the loop. Reaching this line means no divisor was found. - Start a counter. In
countPrimes,let count = 0. - Loop over
numswithfor...of. A number that appears twice is visited twice. - Call the helper in the
if.this.isPrime(num)is alreadytrueorfalse, so no comparison is needed. When it istrue,count++adds 1. - Return
countafter the loop, so every number is checked first.
The solution in JavaScript
class Solution {
isPrime(n) {
if (n < 2) {
return false;
}
for (let d = 2; d < n; d++) {
if (n % d == 0) {
return false;
}
}
return true;
}
countPrimes(nums) {
let count = 0;
for (let num of nums) {
if (this.isPrime(num)) {
count++;
}
}
return count;
}
}
Details worth knowing:
%is the remainder.9 % 3is 0 and7 % 3is 1. A remainder of 0 means an even division.==works here,===is the habit. Both sides are numbers, son % d == 0behaves the same asn % d === 0. Use===in your own code to avoid the type conversions that==performs.- Don't write
if (this.isPrime(num) == true). It works, but the call is already a boolean, so the comparison adds nothing. - Use
this.to call the helper. A bareisPrime(num)inside a class method raises aReferenceError. count++adds 1 to the variable, which is whycountis declared withletand notconst.
Complexity
Time. isPrime(n) does at most n - 2 divisions, and only a prime, or a number whose smallest divisor is large, uses nearly all of them. Even-numbered inputs stop at d = 2. The worst case is a prime near 100000, such as 99991, which takes about 100000 steps. With up to k numbers in nums the total is at most about k × max(nums) steps.
Space: O(1). Only a few variables are used.
Edge cases and common mistakes
- 0 and 1. Without the first check,
isPrime(1)would skip the loop (2 is not less than 1) and returntrue. The first check is what makes itfalse. - 2. It is prime, and the loop starts at 2 with
d < nfalse at once, so it returnstruewithout testing anything. - Starting the loop at 1 or ending at
n. Every number is divisible by 1 and by itself, so including either would make every number "not prime". - Counting distinct primes. Repeats count every time.
[7, 10, 7]gives 2, not 1. - Returning inside the counting loop. It checks only the first number.
Why a helper
The question "is this one number prime?" is separate from "how many of these numbers pass that test?". Putting the first question in isPrime keeps both functions short. countPrimes is a plain counting loop that would look the same for any other yes-or-no test, and isPrime can be checked alone before it is used in the loop.
Testing
isPrime(0)andisPrime(1)givefalse;isPrime(2)andisPrime(97)givetrue;isPrime(9)givesfalse.nums = [2, 3, 4, 5, 6]gives3.nums = [0, 1, 9]gives0.nums = [7, 10, 7]gives2.nums = [99991]gives1.
