PrimeNumbers.kt

import kotlin.math.sqrt

fun main() {
    val result1 = findAllPrimesBySieveOfEratosthenes(100)
    val result2 = findAllPrimesByBruteForce(100)

    println(result1.joinToString())
    println(result2.joinToString())
}

// эффективно работает за O(n*log(log n)), 
// но мы должны хранить массив всех множителей, который может не влезть в память jvm
fun findAllPrimesBySieveOfEratosthenes(n: Int): List<Int> {
    if (n <= 1) {
        throw IllegalArgumentException("n must be greater 1")
    }

    val factors = BooleanArray(n) { true }

    var i = 2
    while (i * i <= n) {
        if (i * i <= 0) throw Exception(i.toString())
        if (factors[i - 1]) {
            var j = i * i
            while (j <= n) {
                factors[j - 1] = false
                j += i
            }
        }
        i++
    }

    return factors.withIndex().filter { it.index > 0 && it.value }.map { it.index + 1 }
}


// работает за O(n * sqrt(n)), но не требует создавать массив всех множителей
fun findAllPrimesByBruteForce(n: Int): List<Int> {
    if (n <= 1) {
        throw IllegalArgumentException("n must be greater 1")
    }

    return (2..n).filter { it.isPrime() }
}

fun Int.isPrime(): Boolean {
    if (this == 2) return true
    val interval = 1..(sqrt(this.toDouble()).toInt() + 1)

    var counter = 0
    for (factor in interval) {
        if (this % factor == 0) {
            counter++
        }
    }

    return counter == 1
}