Kotlin : list of primes till n

Question

I am trying to make a function in kotlin to return list of primes till input argument n. I have tried below code but it is returning list with multiple same digits.

/**
 * You can edit, run, and share this code. 
 * play.kotlinlang.org 
 */

fun main() {
    
    fun primes(n : Int):MutableList<Int>{
        var li : MutableList<Int> = mutableListOf(2)
        for(num in 2..n+1){
            for(i in 2..num){
                if(num % i == 0)
                break
                else
                li.add(num)
            }
        }
        return li
    }
    
    print(primes(7))
}

Output :

[2, 3, 5, 5, 5, 7, 7, 7, 7, 7]

What's wrong in my code ?

Answer 1

This is a prime example (!) of where a loop can be replaced by more functional-style code — in this case, the none() function:

fun primes(n: Int): MutableList<Int> {
    val li = mutableListOf<Int>()
    for (num in 2..n) {
        if ((2 until num).none{ num % it == 0 })
            li.add(num)
    }
    return li
}

To explain: the none() function returns true only if the lambda returns false for every item of the list.  And it means the parameter value (imagine it -> in the lambda).  So it's checking that num can be divided by none of the numbers from 2 to num-1 (which is of course the definition of a prime).  This is not only shorter, but also hopefully easier to read.  (Once you're used to the functional style, of course.)

In fact, you can replace the outer loop too, and make the whole thing a one-liner:

fun primes(n: Int)
    = (2..n).filter{ num -> (2 until num).none{ num % it == 0 } }

That version is purely functional, but perhaps a little too compressed to be easily readable.  It takes the numbers from 2 to n, and keeps only those which are prime (as described above).  (filter() returns a list, so there's no need to create one manually.)

However, in algorithmic terms, there's no need to check every possible divisor up to the number you're testing — you only need to check for the prime divisors.  That's a more efficient approach.  Because it uses the list of primes you've already found, you can't do it with a simple filter() as in the second example.  But you can easily tweak the first example to do that: just replace the if ((2 until num).none{ with if (li.none{.

Answer 2

try this code

    fun primes(n : Int):MutableList<Int>{
        var li : MutableList<Int> = mutableListOf(2)
        for(num in 2..n+1){
            for(i in 2..num){
                if(num % i == 0){
                    if(num==i) li.add(num) else break
                } 
            }
        }
        return li
    }

basically you break when num is divisible by i and they're not the same number
this will fix adding the number for every non divisible number smaller than num