Start learning free

LESSON 133 OF 348 · LOOPS & CONDITIONALS

Prime Number in TypeScript: O(n) Trial Division with a for Loop

Practice Read the full explanation

Given a non-negative integer n check if it is a prime number

Prime numbers are positive numbers greater than 1 that are divisible only by 1 and the number itself.

Examples of prime numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23

Example 1:

Input: n = 31
Output: true

Example 2:

Input: n = 6
Output: false
Explanation: 6 is divisible by 2 and 3.

Note:

Your algorithm should run in O(n) time and use O(1) space.


Hints:

Prime numbers are only divisible by the number 1 or itself. Let's reformulate this definition a little bit:
A number n is prime if and only if there is no such number d such that 1 < d < n and d is a divisor of n. Is this new definition more helpful?

We should iterate through each number d from 2 to n - 1 and check if d is a divisor of n.
If we find such a number, we can conclude that n is not prime and return false right away: 
for each d : 2 -> n - 1:
	if d is divisor of n:
		return false
How do we check if d is divisor of n? When should we return true?

d is divisor of n (or n is a multiple of d) if and only if n % d == 0: 
for each d : 2 -> n - 1:
	if n % d == 0:
		return false
return true
As you can see, if the for loop terminates and we reach the return true line of code, we know that we haven't found a divisor, so it's safe to say n is prime.

We have a for loop that performs exactly n - 2 iterations, thus the Time Complexity is O(n).
The only extra space we use is the iterator variable i inside the loop, thus the Extra Space used is O(1).

STEP 1 OF 4
    Ctrl + Enter to check

    TYPESCRIPT · LOOPS & CONDITIONALS

    Prime Number in TypeScript, explained

    Problem overview

    The method isPrime receives a non-negative integer n and returns true if it is prime and false if it is not. A prime number is greater than 1 and divisible only by 1 and itself. For n = 31 the answer is true. For n = 6 the answer is false, because 6 is divisible by 2 and 3.

    The statement asks for O(n) time and O(1) extra space. That tells you a plain loop that tries the possible divisors one by one is acceptable, and that you should not store anything proportional to n.

    Approach: look for a divisor

    The definition is about divisors, so it is easier to turn it around. A number n is prime exactly when it is at least 2 and there is no number d with 1 < d < n that divides it evenly. Checking for the absence of something is a familiar pattern: search for a counterexample, and if you find one, answer false immediately. If the search ends without finding one, the answer is true.

    The candidates for d are 2, 3, ..., n - 1. A number d divides n when the remainder of n / d is zero, which TypeScript writes as n % d === 0.

    That takes about n - 2 remainder checks in the worst case, which is the O(n) the statement asks for. Faster methods exist, such as stopping the search at the square root of n, but this lesson uses the simplest version.

    Numbers below 2 need their own rule, since the definition excludes them: 0 and 1 are not prime.

    Step by step

    1. Reject the numbers below 2. Test n < 2 first and return false. This covers 0 and 1. The loop would not run for either of them, so without this line the method would wrongly return true.
    2. Loop over the candidate divisors. A for loop with the variable d starts at 2 and runs while d < n, so the last value is n - 1. Starting at 1 would be wrong, since every number is divisible by 1, and including n would be wrong for the same reason.
    3. Test divisibility. Inside the loop, if n % d === 0, then d divides n, and n is not prime. Return false right away, which ends the whole method.
    4. Return true at the end. If the loop finishes, no divisor was found, so n is prime. For n = 2 the loop does not run at all, and for n = 3 its only pass finds that 2 does not divide 3, so both correctly end up here.

    The solution in TypeScript

    class Solution {
    isPrime(n: number): boolean {
        if (n < 2) {
            return false;
        }
        for (let d = 2; d < n; d++) {
            if (n % d === 0) {
                return false;
            }
        }
        return true;
    }
}

    Some TypeScript details about this code:

    • One numeric type. There is no separate integer type, so n and d are both number, a double-precision floating-point value. The code relies on the input being a whole number. Calling isPrime(2.5) returns true in this code, because 2.5 % 2 is 0.5 and the loop ends at d = 3. The annotation n: number does not rule decimals out, and nothing is checked at run time.
    • The remainder operator. % works on numbers and returns the remainder with the sign of the left operand. For a non-negative n and a positive d the result is never negative, so comparing with 0 is safe.
    • Strict equality. === compares without converting types. It is the comparison to use in TypeScript.
    • No overflow. A number keeps integers exact up to 2^53, which is far beyond what a loop of this kind can reasonably reach, so there is no wrap-around to worry about.
    • The loop variable is local. let d exists only inside the for statement, and the name is not visible after the loop ends.

    Complexity

    Time: O(n). The loop runs at most n - 2 times, and each pass does one remainder and one comparison. For a composite number it often stops much earlier, since the smallest divisor ends the search. Primes are the worst case, because they run the whole loop.

    Space: O(1). The method uses only the variables n and d.

    Edge cases and common mistakes

    • 0 and 1 are not prime. The guard at the top handles them. Both give false.
    • 2 is prime. It is the only even prime. With n = 2 the loop starts at d = 2 and the condition d < n is already false, so the method returns true.
    • Starting the loop at 1. Every number gives remainder 0 when divided by 1, so every number would be reported as not prime.
    • Looping up to and including n. Every number is also divisible by itself, which leads to the same wrong answer.
    • Returning true inside the loop. Finding one d that does not divide n says nothing about the others. Only the end of the loop proves there is no divisor.
    • Using / for the test. In TypeScript, 6 / 4 is 1.5, not a whole number with a remainder. Divisibility is tested with %.
    • Negative input. The task promises non-negative values, but the guard also makes -7 return false.

    Testing

    • n = 31 gives true, and n = 6 gives false.
    • n = 0 and n = 1 give false.
    • n = 2 and n = 3 give true.
    • n = 9 gives false, and n = 97 gives true.
    • n = 100 gives false.
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free