Проверьте, является ли число простым в O(sqrt(n)) в Scala

Question

При проверке, если n это простое число в Scala, наиболее распространенные решения - это краткий однострочный текст, который можно увидеть почти во всех похожих вопросах по SO

  def isPrime1(n: Int) = (n > 1) && ((2 until n) forall (n % _ != 0))

Далее, просто переписать его, чтобы проверить только нечетные числа

  def isPrime2(n: Int): Boolean = {
    if (n < 2) return false
    if (n == 2) return true
    if (n % 2 == 0) false
    else (3 until n by 2) forall (n % _ != 0)
  }

Однако, чтобы быть более эффективным, я хотел бы объединить проверку только шансов со счетом до sqrt(n), но без использования Math.sqrt, Таким образом i < sqrt(n) <==> i * i < nЯ бы написал C-подобный цикл:

def isPrime3(n: Int): Boolean = {
    if (n < 2) return false
    if (n == 2) return true
    if (n % 2 == 0) return false
    var i = 3
    while (i * i <= n) {
      if (n % i == 0) return false
      i += 2
    }
    true
  }

Вопросы:

1) Как добиться последней версии в первой версии хорошего функционального стиля Scala?

2) Как я могу использовать Scala for к этому? Я думал о чем-то похожем ниже, но не знаю как.

for {
    i <- 3 until n by 2
    if i * i <= n
  } { ??? }

Answer 1

Вот метод, чтобы проверить, является ли n простым, пока sqrt(n) без использования sqrt:

  def isPrime3(n: Int): Boolean = {
    if (n == 2) {
      true
    } else if (n < 2 || n % 2 == 0) {
      false
    } else {
      Stream.from(3, 2).takeWhile(i => i * i < n + 1).forall(i => n % i != 0)
    }
  }

Если вы хотите сделать это до n/2, что также является возможной оптимизацией (хуже, чем sqrt(n)), вы можете заменить последнюю строку на:

 (3 to n/2 + 1 by 2).forall(i => n % i != 0)

Если вы предпочитаете, вы также можете сделать хвостовую рекурсивную версию, примерно такую:

  import scala.annotation.tailrec

  def isPrime3(n: Int): Boolean = {
    if (n == 2 || n == 3) {
      true
    } else if (n < 2 || n % 2 == 0) {
      false
    } else {
      isPrime3Rec(n, 3)
    }
  }

  @tailrec
  def isPrime3Rec(n:Int, i: Int): Boolean = {
    (n % i != 0) && ((i * i > n) || isPrime3Rec(n, i + 2))
  }