Напишите котлин-функцию isPrimeNumber

Упражнение:
Напишите тест на простое число isPrime (num: Int), который для целого числа m> = 2 проверяет, является ли целое число простым или нет.

Мое решение:

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
}

Может ли мое решение стать более эффективным с точки зрения эффективности?

Два простых улучшения

Найдите квадратный корень из n, а не n / 2. Таким образом, для 101 вам нужно всего лишь проверить n до 10, а не 50. Если ваше число не является простым, то 1 из его множителей должен быть меньше, чем он равен его квадратному корню.

Не проверяйте число, кратное 2, поэтому проведите один тест, чтобы увидеть, можно ли разделить число на 2, а затем проверяйте только нечетные числа, начинающиеся с 3.

Итак, если вы проверяете 101 на простоту, эти изменения означают, что вместо проверки делимости на 2..50 вы проверяете только 2,3,5,7,9

Другие вещи, которые следует учитывать

Используйте простые числа ниже квадратного корня n. Итак, если вы знаете, что 2,3,5,7 — единственные простые числа, меньшие квадратного корня из 101, вам нужно только проверить делимость на эти числа, чтобы показать, что 101 — простое число.

Более сложным решением было бы взглянуть на детерминированную версию теста Миллера Рабина, как описано здесь это хорошо работает, если вы просто хотите знать, является ли конкретное значение простым.

Наиболее эффективным, если вы хотите, чтобы все простые числа меньше n, были бы сито простых чисел