Question

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

Answer 1

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

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

    maxPFact
  }

  def main(args: Array[String]): Unit = {
    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

object Main {

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

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

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

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

    largest
  }

  def main(args: Array[String]): Unit = {

    val n1: Long = 124 // 2 x 2 x 31
    val n2: Long = 288 // 2 x 2 x 2 x 2 x 2 x 3 x 3
    val n3: Long = 1288 // 2 x 2 x 2 x 7 x 23
    val n4: Long = 100000000 // 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5
    val n5: Long = 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