项目Euler - Scala中最大的主要因素

Question

我一直在尝试在Scala中解决3中的项目Euler数,这是我到目前为止所得到的:

def largestPrimeFactor(in:BigInt) : Option[BigInt] = {
  def isPrime(in:BigInt) : Boolean = {
    def innerIsPrime(in:BigInt, currentFactor:BigInt) : Boolean = {
        if(in % currentFactor == 0) {
        false
      }
      else {
        if(currentFactor > (in / 2)){
           true
        }
        else {
          innerIsPrime(in, currentFactor + 1)
        }
      }
    }

     innerIsPrime(in, 2)
  }

   def nextLargeFactor(in:BigInt, divisor:BigInt) : (Option[BigInt], BigInt) = {
     if((in / 2) > divisor) {
       if(in % divisor == 0) (Some(in / divisor), divisor) 
       else nextLargeFactor(in, divisor + 1)
     }
     else
       (None, divisor)
   }

   def innerLargePrime(in : BigInt, divisor:BigInt) : (Option[BigInt], BigInt) = {
     nextLargeFactor(in, divisor) match {
       case (Some(factor), div) => {
         if(isPrime(factor)) (Some(factor), div)
         else innerLargePrime(in, div + 1)
       }
       case (None, _) => (None, divisor)
     }
  }

  innerLargePrime(in, 2)._1
}

我觉得它会起作用,但是我坚持工作(在慢速构建中利用时间)并且只有SimplyScala服务 - 这是超时(我会在家里检查).

但是,这是我写过的任何长度的Scala的第一部分,我想我会问,我犯了什么可怕的罪？我的解决方案多么无可救药？我践踏了哪些约定？

谢谢!

Answer 1

我真的没有得到你想要完成的东西.就这么简单:

def largestPrimeFactor(b : BigInt) = {
  def loop(f:BigInt, n: BigInt): BigInt =
     if (f == n) n else 
     if (n % f == 0) loop(f, n / f) 
     else loop(f + 1, n)
  loop (BigInt(2), b)
}

虽然这里没有优化,但我立刻得到了结果.唯一的"技巧"是你必须知道一个数字的最小因子(大一个)是"自动"素数,并且你可以在找到一个因子后划分数字.