Стиль выглядит хорошо для меня.Хотя сито Эратосфена является очень эффективным способом поиска простых чисел, ваш подход также работает хорошо, поскольку вы проверяете только деление на известные простые числа.Однако вам нужно остерегаться - ваша рекурсивная функция не является хвостовой.Хвостовая рекурсивная функция не изменяет результат рекурсивного вызова - в вашем примере вы добавляете результат к рекурсивному вызову.Это означает, что у вас будет длинный стек вызовов, поэтому 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 также являются изменяемыми типами данных, что вновь соответствует вашему стремлению к функциональному стилю.
Обновление: чтобы добиться хорошей производительности из решета Эратосфена, я думаю, вам нужно будет хранить данныев нативном массиве, что также идет вразрез с вашим стремлением к стилю в функциональном программировании.Хотя может быть творческая функциональная реализация!
Обновление: упс!Пропустил его!Этот подход также хорошо работает , если вы делите только на простые числа меньше квадратного корня числа, которое вы тестируете !Я пропустил это, и, к сожалению, нелегко настроить мое решение, чтобы сделать это, потому что я храню простые числа в обратном направлении.
Обновление: вот очень нефункциональное решение, которое по крайней мере проверяет только до квадратного корня.
rnative, вы можете использовать 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)
Или я мог бы использовать Vector s с моим первоначальным подходом.Vector s, вероятно, не лучшее решение, потому что у них нет ускоренного O (1), хотя это амортизированное O (1).