Найдите простые числа с помощью Scala. Помогите мне улучшить

Стиль выглядит хорошо для меня. Хотя решето Эратосфена — очень эффективный способ нахождения простых чисел, ваш подход тоже работает хорошо, поскольку вы проверяете деление только на известные простые числа. Однако вам нужно следить за тем, чтобы ваша рекурсивная функция не была хвостовой рекурсией. Хвостовая рекурсивная функция не изменяет результат рекурсивного вызова - в вашем примере вы добавляете результат к результату рекурсивного вызова. Это означает, что у вас будет длинный стек вызовов, поэтому findPrime не будет работать для больших i. Вот хвост-рекурсивное решение.

def primesUnder(n: Int): List[Int] = {
  require(n >= 2)

  def rec(i: Int, primes: List[Int]): List[Int] = {
    if (i >= n) primes
    else if (prime(i, primes)) rec(i + 1, i :: primes)
    else rec(i + 1, primes)
  }

  rec(2, List()).reverse
}

def prime(num: Int, factors: List[Int]): Boolean = factors.forall(num % _ != 0)

Это решение не красивее - это больше деталей, чтобы заставить ваше решение работать с большими аргументами. Поскольку список построен в обратном порядке, чтобы использовать преимущества быстрых префиксов, список необходимо перевернуть. В качестве альтернативы вы можете использовать Array, Vector или ListBuffer для добавления результатов. Однако с Array вам нужно будет оценить, сколько памяти выделить для него. К счастью, мы знаем, что pi(n) примерно равно n / ln(n), поэтому вы можете выбрать разумный размер. Array и ListBuffer также являются изменяемыми типами данных, что опять-таки соответствует вашему стремлению к функциональному стилю.

Обновление: чтобы получить хорошую производительность от решета Эратосфена, я думаю, вам нужно хранить данные в собственном массиве, что также противоречит вашему стремлению к стилю функционального программирования. Однако может быть творческая функциональная реализация!

Обновление: ой! Пропустил его! Этот подход также хорошо работает, если вы делите только на простые числа, меньшие квадратного корня из числа, которое вы тестируете! Я пропустил это, и, к сожалению, нелегко настроить мое решение для этого, потому что я храню простые числа в обратном порядке.

Обновление: вот очень нефункциональное решение, которое, по крайней мере, проверяет только квадратный корень.

Обычно вы можете использовать Array, Vector или ListBuffer для добавления результатов. Однако с Array вам нужно будет оценить, сколько памяти выделить для него. К счастью, мы знаем, что pi(n) примерно равно n / ln(n), поэтому вы можете выбрать разумный размер. Array и ListBuffer также являются изменяемыми типами данных, что опять-таки соответствует вашему стремлению к функциональному стилю.

Обновление: чтобы получить хорошую производительность от решета Эратосфена, я думаю, вам нужно хранить данные в собственном массиве, что также противоречит вашему стремлению к стилю функционального программирования. Однако может быть творческая функциональная реализация!

Обновление: ой! Пропустил его! Этот подход также хорошо работает, если вы делите только на простые числа, меньшие квадратного корня из числа, которое вы тестируете! Я пропустил это, и, к сожалению, нелегко настроить мое решение для этого, потому что я храню простые числа в обратном порядке.

Обновление: вот очень нефункциональное решение, которое, по крайней мере, проверяет только квадратный корень.

import scala.collection.mutable.ListBuffer

def primesUnder(n: Int): List[Int] = {
  require(n >= 2)

  val primes = ListBuffer(2)
  for (i <- 3 to n) {
    if (prime(i, primes.iterator)) {
      primes += i
    }
  }

  primes.toList
}

// factors must be in sorted order
def prime(num: Int, factors: Iterator[Int]): Boolean = 
  factors.takeWhile(_ <= math.sqrt(num).toInt) forall(num % _ != 0)

Или я мог бы использовать Vectors с моим первоначальным подходом. Vectors, вероятно, не лучшее решение, потому что у них нет поста O (1), даже если он амортизирован O (1).

Вот функциональная реализация решета Эратосфена, представленная в Курс Одерски "Принципы функционального программирования на Scala" Coursera:

  // Sieving integral numbers
  def sieve(s: Stream[Int]): Stream[Int] = {
    s.head #:: sieve(s.tail.filter(_ % s.head != 0))
  }

  // All primes as a lazy sequence
  val primes = sieve(Stream.from(2))

  // Dumping the first five primes
  print(primes.take(5).toList) // List(2, 3, 5, 7, 11)

Как упоминает schmmd, вы хотите, чтобы он был хвостовым рекурсивным, и вы также хотите, чтобы он был ленивым. К счастью, для этого есть идеальная структура данных: Stream.

Это очень эффективный простой калькулятор, реализованный как Stream с несколькими оптимизациями:

object Prime {
  def is(i: Long): Boolean =
    if (i == 2) true
    else if ((i & 1) == 0) false // efficient div by 2
    else prime(i)

  def primes: Stream[Long] = 2 #:: prime3

  private val prime3: Stream[Long] = {
    @annotation.tailrec
    def nextPrime(i: Long): Long =
      if (prime(i)) i else nextPrime(i + 2) // tail

    def next(i: Long): Stream[Long] =
      i #:: next(nextPrime(i + 2))

    3 #:: next(5)

  }

    // assumes not even, check evenness before calling - perf note: must pass partially applied >= method
  def prime(i: Long): Boolean =
    prime3 takeWhile (math.sqrt(i).>= _) forall { i % _ != 0 }
}

Prime.is — это предикат проверки простых чисел, а Prime.primes возвращает Stream всех простых чисел. prime3 — это место, где вычисляется Stream, используя предикат prime для проверки всех простых делителей, меньших квадратного корня из i.

Метод сита лучше всего подходит для небольших списков чисел (до 10-100 миллионов или около того). см.: Решето Эратосфена

Даже если вы хотите найти гораздо большие числа, вы можете использовать список, созданный с помощью этого метода, в качестве делителей для проверки чисел до n ^ 2, где n — это предел вашего списка.

@mfa упомянул об использовании решета Эратосфена - SoE, а @Luigi Plinge упомянул, что это должно быть сделано с использованием функционального кода, поэтому @netzwerg опубликовал версию, не относящуюся к SoE; здесь я публикую «почти» функциональную версию SoE, использующую полностью неизменное состояние, за исключением содержимого изменяемого BitSet (изменяемого, а не неизменного для производительности), который Я разместил ответ на другой вопрос:

object SoE {
  def makeSoE_Primes(top: Int): Iterator[Int] = {
    val topndx = (top - 3) / 2
    val nonprms = new scala.collection.mutable.BitSet(topndx + 1)
    def cullp(i: Int) = {
      import scala.annotation.tailrec; val p = i + i + 3
      @tailrec def cull(c: Int): Unit = if (c <= topndx) { nonprms += c; cull(c + p) }
      cull((p * p - 3) >>> 1)
    }
    (0 to (Math.sqrt(top).toInt - 3) >>> 1).filterNot { nonprms }.foreach { cullp }
    Iterator.single(2) ++ (0 to topndx).filterNot { nonprms }.map { i: Int => i + i + 3 }
  }
}

Как насчет этого.

def getPrimeUnder(n: Int) = {
  require(n >= 2)
  val ol = 3 to n by 2 toList // oddList
  def pn(ol: List[Int], pl: List[Int]): List[Int] = ol match {
    case Nil => pl
    case _ if pl.exists(ol.head % _ == 0) => pn(ol.tail, pl)
    case _ => pn(ol.tail, ol.head :: pl)
  }
  pn(ol, List(2)).reverse
}

Для меня на моем Mac довольно быстро получить все праймы ниже 100k, это занимает около 2,5 секунд.

Скалярный метод fp

// returns the list of primes below `number`
def primes(number: Int): List[Int] = {
    number match {
        case a
        if (a <= 3) => (1 to a).toList
        case x => (1 to x - 1).filter(b => isPrime(b)).toList
    }
}

// checks if a number is prime
def isPrime(number: Int): Boolean = {
    number match {
        case 1 => true
        case x => Nil == {
            2 to math.sqrt(number).toInt filter(y => x % y == 0)
        }
    }
}