Start learning free

LESSON 241 OF 671 · HELPER FUNCTIONS

Count Primes in JavaScript: A Helper and a Loop

Practice Read the full explanation

Given an array of integers nums, return how many of them are prime numbers.

A prime number is greater than 1 and can be divided evenly only by 1 and by itself: 2, 3, 5, 7, 11, 13 and so on. 0 and 1 are not prime. If a number appears more than once, each appearance counts.

The work is split between two functions. The first one is a helper: it gets one number and returns true if it is prime, false if it is not. The second one, the function that is graded, goes over the numbers and counts the ones the helper says are prime.

 

Example 1:

Input: nums = [2, 3, 4, 5, 6]
Output: 3
Explanation: 2, 3 and 5 are prime. 4 = 2 × 2 and 6 = 2 × 3 are not.

Example 2:

Input: nums = [0, 1, 9]
Output: 0
Explanation: 0 and 1 are never prime, and 9 = 3 × 3.

Example 3:

Input: nums = [7, 10, 7]
Output: 2
Explanation: 7 is prime and appears twice, so it counts twice. 10 = 2 × 5 is not prime.

 

Constraints:

  • nums has at least one number.
  • Every number is an integer from 0 to 100000.
STEP 1 OF 8
    Ctrl + Enter to check

    JAVASCRIPT · HELPER FUNCTIONS

    Count Primes in JavaScript, explained

    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

    1. Reject numbers below 2. In isPrime, if (n < 2) returns false. This covers 0 and 1.
    2. Write the divisor loop. d starts at 2 and goes up while d < n, so it tries every number from 2 to n - 1.
    3. Test for a divisor. If n % d == 0, the remainder is zero and d divides n evenly. Return false: the return ends both the loop and the function.
    4. Return true after the loop. Reaching this line means no divisor was found.
    5. Start a counter. In countPrimes, let count = 0.
    6. Loop over nums with for...of. A number that appears twice is visited twice.
    7. Call the helper in the if. this.isPrime(num) is already true or false, so no comparison is needed. When it is true, count++ adds 1.
    8. Return count after 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 % 3 is 0 and 7 % 3 is 1. A remainder of 0 means an even division.
    • == works here, === is the habit. Both sides are numbers, so n % d == 0 behaves the same as n % 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 bare isPrime(num) inside a class method raises a ReferenceError.
    • count++ adds 1 to the variable, which is why count is declared with let and not const.

    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 return true. The first check is what makes it false.
    • 2. It is prime, and the loop starts at 2 with d < n false at once, so it returns true without 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) and isPrime(1) give false; isPrime(2) and isPrime(97) give true; isPrime(9) gives false.
    • nums = [2, 3, 4, 5, 6] gives 3.
    • nums = [0, 1, 9] gives 0.
    • nums = [7, 10, 7] gives 2.
    • nums = [99991] gives 1.
    Keep going with JavaScript650+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free