Почему это поколение scala prime так медленно / требует много памяти?

Мне не хватает памяти при нахождении 10 001-го простого числа.

object Euler0007 {
  def from(n: Int): Stream[Int] = n #:: from(n + 1)
  def sieve(s: Stream[Int]): Stream[Int] = s.head #:: sieve(s.filter(_ % s.head != 0))
  def primes = sieve(from(2))
  def main(args: Array[String]): Unit = {
    println(primes(10001))
  }
}

Это потому, что после каждой «итерации» (правильный ли это термин в данном контексте?) простых чисел , Я увеличиваю стек вызываемых функций для получения следующего элемента на единицу?

Одно решение, которое я нашел в Интернете, которое не прибегает к итеративному решению (которого я бы хотел избежать, чтобы войти в функциональное программирование / идиоматику scala) this (Проблема 7):

lazy val ps: Stream[Int] = 2 #:: Stream.from(3).filter(i => ps.takeWhile(j => j * j <= i).forall(i % _ > 0))

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

6
задан Will Ness 13 June 2018 в 19:34
поделиться