Question

How to find the largest prime factor of a number in Kotlin

Answer 1

fun largestPrimeFactor(n: Long): Long {
    var num = n
    var div = 2L
    var maxPFact = -1L

    while (num != 0L) {
        if (num % div != 0L) {
            div++
        } else {
            maxPFact = num
            num /= div // Integer division
            if (num == 1L) {
                return maxPFact
            }
        }
    }

    return maxPFact
}

fun main() {
    println(largestPrimeFactor(124))  // 2 x 2 x 31
    println(largestPrimeFactor(288))  // 2 x 2 x 2 x 2 x 2 x 3 x 3
    println(largestPrimeFactor(1288)) // 2 x 2 x 2 x 7 x 23
    println(largestPrimeFactor(100000000)) // 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5
}

   
      
/*
run:

31
3
23
5
  
*/

 

70+ SQL courses for beginners and professionals

Answer 2

// Returns the largest prime factor of n
fun largestPrimeFactor(n: Long): Long {
    var num = n
    var largest: Long = -1

    // Step 1: Remove all factors of 2
    while (num % 2L == 0L) {
        largest = 2
        num /= 2
    }

    // Step 2: Try odd factors from 3 to sqrt(n)
    var i = 3L
    while (i * i <= num) {
        while (num % i == 0L) {
            largest = i
            num /= i
        }
        i += 2
    }

    // Step 3: If n is still > 2, it is a prime number
    if (num > 2) {
        largest = num
    }

    return largest
}

fun main() {
    val n1 = 124L // 2 x 2 x 31
    val n2 = 288L // 2 x 2 x 2 x 2 x 2 x 3 x 3
    val n3 = 1288L // 2 x 2 x 2 x 7 x 23
    val n4 = 100000000L // 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5
    val n5 = 600851475143L // 71, 893, 1471, 6857

    println("Largest prime factor: ${largestPrimeFactor(n1)}")
    println("Largest prime factor: ${largestPrimeFactor(n2)}")
    println("Largest prime factor: ${largestPrimeFactor(n3)}")
    println("Largest prime factor: ${largestPrimeFactor(n4)}")
    println("Largest prime factor: ${largestPrimeFactor(n5)}")
}


/*
run:

Largest prime factor: 31
Largest prime factor: 3
Largest prime factor: 23
Largest prime factor: 5
Largest prime factor: 6857

*/

 

70+ SQL courses for beginners and professionals