Kotlin recursive function: Check prime number

Last update on February 04 2025 08:27:16 (UTC/GMT +8 hours)

Write a Kotlin recursive function to check if a number is a prime number.

Pre-Knowledge (Before You Start!)

Before solving this exercise, you should understand these concepts:

• Prime Number: A number greater than 1 that has no divisors other than 1 and itself.
• Recursive Function: A function that calls itself with modified arguments to break down a problem.
• Base Case: A condition where recursion stops to prevent infinite loops.
• Efficient Prime Check: A number is prime if it is not divisible by any integer from 2 to its square root.

Hints (Try Before Looking at the Solution!)

Here are some hints to help you solve the problem:

• Hint 1: A prime number has exactly two divisors: 1 and itself.
• Hint 2: The base case should return false if n <= 1.
• Hint 3: If current * current > n, then n is prime.
• Hint 4: If n is divisible by current, it is not a prime number.
• Hint 5: Use recursion to test divisibility by incrementing current until it reaches the square root of n.

Sample Solution:

Kotlin Code:

fun isPrime(n: Int, current: Int = 2): Boolean {
    if (n <= 1) {
        return false
    }

    if (current * current > n) {
        return true
    }

    if (n % current == 0) {
        return false
    }

    return isPrime(n, current + 1)
}

fun main() {
    val number = 37
    //val number = 38
    val isPrimeNumber = isPrime(number)
    val message = if (isPrimeNumber) "is a prime number." else "is not a prime number."
    println("$number $message")
}

Sample Output:

37 is a prime number.
38 is not a prime number.

Explanation:

In the above exercise -

The "isPrime()" function takes two parameters: n (the number to check for primality) and current (the current divisor being tested, initialized to 2).

To determine whether n is prime, the function uses recursion. It follows the following steps:

• Since prime numbers are greater than 1, it returns false if n is less than or equal to 1.
• If the square of current is greater than n, it means we have tested all possible divisors up to the square root of n, and none of them divided n evenly. Thus, n is a prime number, and the function returns true.
• If n is divisible evenly by the current divisor, it means n is not a prime number. The function returns false.
• Otherwise, it calls itself recursively with the same n but increments the current divisor by 1.

In the "main()" function, we define number's value as 37 to check if it's a prime number. We call the "isPrime()" function with this number and store the result in the isPrimeNumber variable. The result is then printed to the console.

Kotlin Editor:

Previous: Find the nth term of arithmetic sequence.
Next: Print even numbers from an array.