Unable to use .to() operator on Long data type

Question

The question is: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?

I have written a code for it but it gives an error.The code is written in Scala.

@main def m(): Unit = {
  var largest = 0L;
  val num = 600851475143L;
  2.to(num - 1).foreach(arg =>
    if num % arg == 0 && largest < arg then
      var flag = true;
      2.to(arg - 1).foreach(arg2 =>
        if arg % arg2 == 0 then flag = false);
      if flag then largest = arg;
  )
  println(largest);
}

The code gives an error of: Found: Long Required: Int 2.to(num - 1).foreach(arg =>

How can we use .to() operator for Long datatype? It seems like we are only allowed to use Int.

I tried type casting the long to the Int but it resulted in the answer getting 0.

Answer 1

While number in a Range can be Longs, they cannot contain more than Int.MaxValue values (docs):

Any method that could require a collection of over Int.MaxValue length to be created, or could be asked to index beyond Int.MaxValue elements will throw an exception.

You can create a lazy Iterator that spans all numbers from 2L to a Long greater than Int.MaxValue as follows:

Iterator.iterate(2L)(_ + 1).takeWhile(_ < max)

So in your code this would be the following:

@main def m(): Unit = {
  var largest = 0L;
  val num = 600851475143L;
  
  Iterator.iterate(2L)(_ + 1).takeWhile(_ < (num - 1)).foreach(arg =>
    if num % arg == 0 && largest < arg then
      var flag = true;
      Iterator.iterate(2L)(_ + 1).takeWhile(_ < (arg - 1)).foreach(arg2 =>
        if arg % arg2 == 0 then flag = false);
      if flag then largest = arg;
  )
  println(largest);
}

A few additional notes:

• you can drop the semicolons if you want, they are not needed in Scala
• producing the range lazily is a bit of a mouthful, it's probably best to give it a name
• you can use for-comprehensions as a way to express looping (what you are achieving with foreach)

Given this, one way to re-write your program could be the following:

def range(from: Long, to: Long, step: Long = 1) = {
  require(from < to)
  Iterator.iterate(from)(_ + step).takeWhile(_ < to)
}

var largest = 0L;
val num = 600851475143L;

for (arg <- range(from = 2L, to = num - 1)) {
  if num % arg == 0 && largest < arg then
    var flag = true
    for (arg2 <- range(from = 2L, to = arg - 1)) {
      if arg % arg2 == 0 then flag = false
    }
    if flag then largest = arg
}

println(largest)

The for-comprehension above is entirely equivalent to a foreach. They are particularly useful when you need to nest multiple flatMaps and close with a map or a foreach to make the code less nested and possibly easier to read. You can read more about them in the documentation.

You can play around with this code here on Scastie. Maybe consider giving your variables names more meaningful than arg, arg2 and flag as well to improve the readability.

As a final note, more important than anything, your algorithm can probably be improved in terms of time complexity, but that's something you want to spent some time on by yourself. ;-)