Project Euler - крупнейший главный фактор в Scala - PullRequest
Новая
       8

Project Euler - крупнейший главный фактор в Scala

0 голосов
/ 20 января 2011

Я пытался решить проект Номер Эйлера в 3 в Scala, и вот что я получил до сих пор: 

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 - время ожидания (я проверю это дома).

Но так как это первый кусочек Скалы любой длины, который я написал, я подумал, что спрошу, какие ужасные грехи я совершил? Насколько безнадежно неоптимальным является мое решение? Какие условности я растоптал?

Спасибо!

Ответы [ 2 ]

9 голосов
/ 20 января 2011

Я не совсем понимаю, чего вы пытаетесь достичь.Это так просто: 

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

Хотя здесь нет ничего оптимизированного, я получаю результат мгновенно.Единственные «уловки» - это то, что вы должны знать, что наименьший фактор (большее значение) числа является «автоматически» простым числом, и что вы можете разделить число, когда вы нашли фактор.

1 голос
/ 18 февраля 2011

Взято из здесь : 

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 ваш ответ

...