Как я могу оптимизировать свою функцию ProperFractions для длинных типов значений

Question

Я работаю над проблемой codewars Количество правильных дробей со знаменателем d . Я пробовал разные подходы к оптимизации решения, но ни один из них не может решить для очень больших чисел за отведенное время.

У кого-нибудь есть какие-либо советы, как оптимизировать код?

Код: https://scastie.scala-lang.org/t0KvxqGuTMKj6zsiiEzn5Q

import scala.annotation.tailrec

def isPrime(n: Long): Boolean = !(2 +: (3 to Math.sqrt(n).toInt by 2) exists (n % _ == 0))
@tailrec private def gcd(a: Long, b: Long): Long = if (b == 0) a else gcd(b, a % b)

def properFractions1(n: Long): Long = {
  var product: Long = n
  var i: Long = 2
  if(n == 1) 0L
  else if(n == 2) 1L
  else {
      while(i <= n) {
          if(isPrime(i) && n%i == 0)
              product = Math.round(product * (1.0-1.0/i))
          i+=1
      }
      product
  }
}

def properFractions2(n: Long): Long = {
  Iterator.iterate(1L)(_ + 1).takeWhile(_ < n)
  .map(gcd(_,n)).filter(_ == 1).sum.toLong
}

def properFractions3(n: Long): Long = {
  val v = for(i <- 1L until n) yield {
      if(isPrime(i) && n%i != 0) 1L
      else if(gcd(i,n) == 1) 1L
      else 0L
  }
  v.sum
}

def properFractions4(n: Long): Long = {
  (1L until n).view.map(gcd(_,n)).filter(_ == 1).sum.toLong
}

properFractions1(15) // 8: Long
properFractions2(15) // 8: Long
properFractions3(15) // 8: Long
properFractions4(15) // 8: Long

// properFractions1(4665289405L)

Answer 1

Иногда описание онлайн-вызова кода достаточно удалено из решения, оно может квалифицироваться как неверное направление .

Чаще всего, когда вы обнаружите, что ваш код отлично решение истекло, никакая оптимизация не собирается это исправить. Обычно это означает, что вам нужно переосмыслить алгоритм базового c.

Для меня "а-ха!" настал момент, когда я понял, что:

ProperFractions(a*b) == ProperFractions(a) * ProperFractions(b)

Соедините это с фактом для любого простого числа p, ProperFractions(p) == p-1, и у нас есть четкое указание на то, что вы могли бы делить и победить. (Scala решение в 9 строках кода.)