CODEWITHSUNDEEP
scalaprime-factoring
Massif
Massif

Reputation: 4433

Project Euler - Largest prime factor in Scala

I've been trying to solve project Euler number in 3 in Scala, and this is what I've got so far:

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
}

Which I think will work, but I'm stuck at work (making use of time during slow builds) and only have the SimplyScala service - which is timing out (I'll check it at home).

But as this is the first bit of Scala of any length I've written I'd thought I'd ask, what horrendous sins have I committed? How hopelessly suboptimal is my solution? What conventions have I trampled on?

Thanks!

Upvotes: 0

Views: 1412

Answers (2)

Łukasz Lew
Łukasz Lew

Reputation: 50328

Taken from 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 is your answer

Upvotes: 1

Landei
Landei

Reputation: 54584

I don't really get what you try to accomplish. It's that simple:

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

Although there is nothing optimized here, I get the result instantly. The only "tricks" are that you have to know that the smallest factor (greater one) of a number is "automatically" prime, and that you can divide the number once you have found a factor.

Upvotes: 9

Related Questions