プロジェクトオイラー - スカラ

Question

で最大の素因数は

私はScalaでプロジェクトEuler number in 3を解決しようとしてきたが、これは私がこれまで持っているものです：私は仕事だろうと思うが、私は」

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) 
} 

ここでは最適化されていませんが、すぐに結果が得られます。唯一の "トリック"は、数字の最小因子（大きい方）が「自動的に」素数であり、因子を見つけたときに数を分けることができることを知る必要があることです。

Answer 2

がhereから撮影：

lazy val ps: Stream[Int] = 
    2 #:: ps.map(i => 
    Stream.from(i + 1).find(j => 
     ps.takeWhile(k => k * k <= j).forall(j % _ > 0) 
    ).get 
) 

val n = 600851475143L 
val limit = math.sqrt(n) 
val r = ps.view.takeWhile(_ < limit).filter(n % _ == 0).max 

rは、あなたの答え