Scala LazyList求第n个素数触发StackOverflowError原因及优化

错误原因 #

你写的递归版埃氏筛，问题出在递归调用的深度累积上。Scala的LazyList虽然是惰性求值，但每次筛出一个素数时，都会嵌套调用一次sieve方法，这些调用的栈帧会一直保留到对应位置的素数被求值。当你取第6501个素数时，递归深度超过了JVM默认的栈容量，直接触发StackOverflowError。

简单说：素数取的越多，嵌套的sieve调用栈帧就堆得越高，最终撑爆JVM栈。

优化建议 #

方案1：调整JVM栈大小（临时解决） #

运行程序时添加JVM参数增大栈容量，比如：

scala -Xss2m YourProgram.scala

但这只是临时方案，当需要取更大的素数时，依然会遇到栈溢出问题。

方案2：改用迭代式改进筛法（根本解决） #

用迭代方式结合状态跟踪实现筛法，彻底避免递归深度问题，同时提升筛选效率：

def primes: LazyList[Int] = {
  def next(n: Int, composites: Map[Int, List[Int]]): LazyList[Int] = {
    composites.get(n) match {
      case Some(factors) =>
        // 处理当前合数，更新合数标记
        val newComposites = factors.foldLeft(composites - n) { (map, f) =>
          val nextMultiple = n + f
          map.updated(nextMultiple, f :: map.getOrElse(nextMultiple, Nil))
        }
        next(n + 1, newComposites)
      case None =>
        // n是素数，标记其平方开始的倍数
        n #:: next(n + 1, composites.updated(n * n, List(n)))
    }
  }
  next(2, Map.empty)
}

优化点说明：

• 用迭代替代递归，彻底消除栈溢出风险
• 仅从素数的平方开始标记倍数（更小的倍数已被更小的素数处理），减少无效计算
• 用Map跟踪合数对应的素因子，避免重复筛选操作

方案3：优化递归实现（减少栈压力） #

如果坚持用递归风格，可以通过将递归调用转为惰性求值的一部分，减少栈帧累积：

def primes: LazyList[Int] = {
  def sieve(xs: LazyList[Int]): LazyList[Int] = xs.head #:: LazyList.defer(sieve(xs.tail.filter(_ % xs.head != 0)))
  sieve(LazyList.from(2))
}

LazyList.defer会延迟sieve的调用，直到需要求值时才触发，避免提前创建深层递归栈帧，能一定程度上提升可处理的素数数量，但本质还是递归，极端情况下仍可能出现栈溢出。

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