Start learning free

LESSON 133 OF 348 · LOOPS & CONDITIONALS

Prime Number in Kotlin: 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 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

    KOTLIN · LOOPS & CONDITIONALS

    Prime Number in Kotlin, explained

    Problem overview

    The function isPrime receives a non-negative Int named n and returns true if it is a prime number, false otherwise. A prime is a number greater than 1 whose only divisors are 1 and itself. So 31 is prime, while 6 is not, because it is divisible by 2 and 3.

    The statement asks for O(n) time and O(1) extra space. That allows a direct test of every possible divisor, with no extra storage.

    Approach: look for a divisor between 2 and n - 1

    Rephrase the definition: n is prime exactly when it is at least 2 and no number d with 1 < d < n divides it. That turns the question into a search for a counterexample, a divisor in the range 2 to n - 1:

    • If some d divides n, the number is not prime, and the function can return false immediately.
    • If the loop finishes without finding a divisor, the number is prime.

    A number d divides n when the remainder of n / d is zero, which Kotlin writes as n % d == 0.

    Numbers below 2 need separate handling. The values 0 and 1 aren't prime by definition, but a loop over a range like 2 until n is empty for them, so without a guard they would fall through to true.

    Step by step

    1. Handle the small cases first. If n is less than 2, return false. This covers 0 and 1, which are not prime.
    2. Loop over the candidate divisors. Use an Int variable d in a for loop over 2 until n. The range starts at 2 because every number is divisible by 1, and it excludes n because every number is divisible by itself.
    3. Test each candidate. If n % d == 0, then d divides n, so return false at once.
    4. Return true after the loop. No divisor was found, so n is prime.

    The solution in Kotlin

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

    Kotlin details worth noting:

    • 2 until n excludes n. It produces 2, 3, ..., n - 1. The form 2..n would include n and make every number look divisible by itself, so no number would ever be prime.
    • Empty ranges are fine. For n = 2 the range 2 until 2 contains nothing, so the loop body doesn't run and the function returns true. For n = 3 it contains only 2, which doesn't divide 3. No special case is needed for the smallest primes.
    • The remainder operator. % returns the remainder of integer division. 31 % 2 is 1, so 2 doesn't divide 31, while 6 % 2 is 0.
    • Every path returns. The function ends with return true, so the compiler sees a value on every path through the Boolean function.

    Tracing two inputs

    For n = 6 the loop tries d = 2 first. Since 6 % 2 is 0, the function returns false and never tests 3, 4 or 5. For n = 31 the loop tries every d from 2 to 30, and each remainder is non-zero, so the loop ends and the function returns true.

    Complexity

    Time: O(n). For a prime, or for a number whose smallest divisor is large, the loop runs n - 2 times. A number such as 100 stops at 2, since the first divisor found ends the function. The worst case is what the bound describes.

    Space: O(1). The function keeps only the loop variable d.

    The work can be reduced a lot. Divisors come in pairs, so if n has a divisor other than 1 and itself, it has one no larger than the square root of n. Checking only up to that point brings the time down to about O(sqrt(n)). This lesson uses the plain version to practise the loop.

    A faster version

    Here is the square-root idea as a loop. It is a variation for comparison, not the lesson's solution:

    fun isPrimeFast(n: Int): Boolean {
    if (n < 2) {
        return false
    }
    var d = 2
    while (d.toLong() * d <= n) {
        if (n % d == 0) {
            return false
        }
        d++
    }
    return true
}

    The product d * d is computed as a Long on purpose. For n near the top of the Int range, an Int product would overflow and wrap to a negative number, which would break the comparison. This version answers true for 2147483647 after about 46,000 steps, where the plain loop needs about two billion.

    Edge cases and common mistakes

    • 0 and 1. Both return false thanks to the n < 2 guard. Without it they would return true, because the loop has nothing to check.
    • 2. The only even prime. It returns true through the empty loop.
    • Starting the loop at 1. Every number is divisible by 1, so n % 1 == 0 would make the function return false for every input.
    • Including n in the range. The same problem appears at the other end: n % n is 0.
    • Returning true inside the loop. Writing else { return true } after the divisibility test decides from the first candidate only. For 9 it would test 2, see no divisor, and wrongly answer true.
    • Large inputs. A very large prime near the top of the Int range, which is about 2.1 billion, makes this version do about two billion iterations. That's the cost of the O(n) approach.

    Testing

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