Write a Kotlin-function isPrimeNumber

Question

Exercise: Write a prime number-test isPrime(num: Int), which for integer m >= 2 checks, if the integer is a prime number or not.

My solution:

fun main(args: Array<String>) {
    var isPrime: Boolean = false

    for (i in 2..101) {
        isPrime = isPrime(i)

        if (isPrime) {
            println("$i => ${isPrime(i)}")
        }
    }
}

fun isPrime(num: Int): Boolean {
    val upperLimit = num / 2;
    var i = 2

    while (i <= upperLimit) {
        if (num % i == 0) {
            return false
        }
        i++
    }

    return true
}

Could my solution become improved concerning efficiency?

Answer 1

Two easy improvements

Check up to the square root of n rather than n/2. So for 101 you only need to check n up to 10 not 50. If your number isn't prime then 1 of it's factors must be less than it equal to its square root.

Don't check multiples of 2, so do a single test to see if the number can be divided by 2 then only test odd numbers starting at 3.

So if you test 101 for primeness these's changes mean that instead of testing for divisibilty by 2..50 you only test 2,3,5,7,9

Other things to consider

Use the primes below square root n. So if you know that 2,3,5,7 are the only primes below square root of 101 you only need to test for divisibilty by these numbers to show 101 is prime.

A more complex solution would be to look at a deterministic version of the Miller Rabin test as described here this works well if you just want to know if a specific value is prime.

Most efficient if you want all primes below n would be a prime number sieve