Scala求最大质因数代码报错：Long类型无法使用.to()运算符

问题背景 #

已知13195的质因数为5、7、13和29，求数字600851475143的最大质因数。编写的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);
}

报错信息 #

Found: Long
Required: Int
2.to(num - 1).foreach(arg =>)

用户疑问：如何针对Long类型使用.to()运算符？该运算符似乎仅支持Int类型。尝试将Long强制转换为Int，但结果为0，无法解决问题。

解决方案 #

1. 修复类型不匹配问题 #

Scala中Int类型的.to()方法仅接受Int类型参数，你的代码中num是Long类型，num - 1同样是Long，导致类型不兼容。解决方法是把起始值改为Long类型，用2L替代2，这样调用的是Long的.to()方法，支持Long参数：

2L to (num - 1)

2. 优化算法（核心改进） #

原代码遍历范围是2到num-1，且对每个数都做质数检查，对于600851475143这种超大数，效率极低，几乎无法运行。更高效的方案是用试除法分解质因数：

• 从最小质数2开始，不断用当前数除以能整除的因数，直到无法整除
• 递增除数（跳过偶数），重复操作直到除数的平方大于当前数
• 最后若剩余的数大于1，它就是最大的质因数

优化后的代码：

@main def findLargestPrimeFactor(): Unit = {
  var num = 600851475143L
  var largest = 0L

  // 先处理所有偶数因数
  while num % 2 == 0 do
    largest = 2L
    num /= 2

  // 处理奇数因数，从3开始每次加2
  var i = 3L
  while i * i <= num do
    while num % i == 0 do
      largest = i
      num /= i
    i += 2

  // 剩余的数若大于1，本身就是质因数
  if num > 1 then
    largest = num

  println(largest)
}

代码说明 #

• 优先处理偶数因数，避免后续重复检查偶数
• 仅遍历奇数除数，大幅减少循环次数
• 每次找到可整除的因数时，直接将原数除以该因数，缩小后续计算范围
• 当除数平方超过当前数时，剩余数值若大于1，必然是未分解完的质因数

内容的提问来源于stack exchange，提问作者Diwash Mainali