Start learning free

LESSON 138 OF 414 · LOOPS & CONDITIONALS

Prime Number in Scala: O(n) Check 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 (d <- 2 until n) {
	// if d is a 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 (d <- 2 until n) {
	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 d inside the loop, thus the Extra Space used is O(1).

STEP 1 OF 4
    Ctrl + Enter to check

    SCALA · LOOPS & CONDITIONALS

    Prime Number in Scala, explained

    Problem overview

    The method isPrime receives a non-negative Int named n and returns true if it is prime. A prime number is greater than 1 and divisible only by 1 and by itself. For example, 31 is prime, so the result is true. 6 is divisible by 2 and 3, so the result is false.

    The statement asks for O(n) time and O(1) extra space. That means one pass over the numbers up to n is welcome, and no collection is needed.

    Approach: look for a divisor

    Restate the definition: n is prime when no number d with 1 < d < n divides it. That turns the problem into a search for a counterexample. Try every d from 2 to n - 1. If any of them divides n evenly, n is not prime and the answer is false right away. If none does, the answer is true.

    A number d divides n exactly when the remainder n % d is 0.

    The definition says primes are greater than 1, so the loop would give the wrong answer for 0 and 1: both have no candidate divisors in the range, and the loop would conclude that they are prime. They need their own check first.

    Step by step

    1. Handle numbers below 2. If n < 2, return false. This covers 0 and 1, which are not prime.
    2. Loop over the candidate divisors. for (d <- 2 until n) gives d the values 2, 3, up to n - 1. The range excludes n itself, which is correct because every number divides itself.
    3. Test divisibility. Inside the loop, if n % d == 0, then d is a divisor between 1 and n, and the method returns false.
    4. Return true. If the loop ends, no divisor was found, so n is prime.

    The solution in Scala

    class Solution {
    def isPrime(n: Int): Boolean = {
        if (n < 2) {
            return false
        }
        for (d <- 2 until n) {
            if (n % d == 0) {
                return false
            }
        }
        return true
    }
}

    The Scala details worth knowing:

    • 2 until n can be empty. For n = 2 it is 2 until 2, which has no elements. The loop body never runs and the method returns true, which is right since 2 is prime. The same happens for 3, whose only candidate is 2, and 2 doesn't divide 3.
    • % is the remainder. Between two Int values, n % d is what is left after integer division. If it is 0, d divides n.
    • Early return in two places. The first return false is directly in the method body. The second sits inside the for body, which Scala treats as a function passed to foreach. Scala 3.5 accepts it and the method works, but the compiler prints a deprecation warning about non-local returns.
    • The result type is satisfied. The method ends with return true, so the compiler sees a Boolean on every path.

    Tracing two inputs

    For n = 9, the loop tries d = 2 first. The remainder of 9 divided by 2 is 1, so nothing happens. Then d = 3: the remainder is 0, so the method returns false and the candidates 4 to 8 are never tried.

    For n = 7, the loop tries 2, 3, 4, 5 and 6. Each leaves a nonzero remainder, the range runs out, and the method returns true. A prime is the slowest case, because the method can't stop until every candidate has been rejected.

    Complexity

    Time: O(n). The loop makes at most n - 2 passes, each with one remainder operation. When n is composite the loop usually stops much sooner. It stops at the smallest divisor, and for an even number that is 2. The worst case is a prime, where every candidate has to be rejected.

    Space: O(1). A range like 2 until n does not store its numbers, so no memory grows with n.

    The loop can be made faster. If n has a divisor, it has one no larger than its square root, so it is enough to try d up to sqrt(n). This lesson keeps the plain version, because the simple search is the part worth learning first.

    Edge cases and common mistakes

    • 0 and 1. Not prime. Without the first check, they would reach the loop, find no divisor and be reported as prime.
    • 2. The smallest prime, and the only even one. It returns true because the range is empty.
    • Starting the loop at 1. Every number is divisible by 1, so n % 1 == 0 would make every n look composite.
    • Including n in the loop. 2 to n reaches d = n, and n % n == 0 always, so even primes would return false.
    • Returning true inside the loop. One candidate that does not divide n proves nothing. Only the end of the loop does.
    • Very large inputs. For a prime near the top of the Int range the loop makes about two billion passes, so the square-root bound matters in practice.

    Testing

    • isPrime(31) gives true.
    • isPrime(6) gives false.
    • isPrime(2) gives true.
    • isPrime(1) and isPrime(0) give false.
    • isPrime(9) gives false, because 3 divides it.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free