p003.scala

package me.sunphiz

object p003 extends App {
  def run(n: Long, p : Long = 2L): Long = {
    var sp = smallestFactor(n, p)
    if (sp < n)
      run(n / sp, sp)
    else
      return n
  }

  def smallestFactor(n: Long, p : Long): Long = {
    var i = p;

    while (i < Math.sqrt(n).toLong) { 
      if (n % i == 0) return i
      i += 1
    }

    return n
  }

  println(run(600851475143L))
}