Why is my algorithm for Project Euler Problem 12 so slow?

Question

I created a solution for PE P12 in Scala, but very slowly. Can someone explain to me why? How to optimize this? calculateDevisors () - naive approach and calculationNumberOfDivisors () - the divider function has the same speed: /

import annotation.tailrec

def isPrime(number: Int): Boolean = {
  if (number < 2 || (number != 2 && number % 2 == 0) || (number != 3 && number % 3 == 0))
    false
  else {
    val sqrtOfNumber = math.sqrt(number) toInt

    @tailrec def isPrimeInternal(divisor: Int, increment: Int): Boolean = {
      if (divisor > sqrtOfNumber)
        true
      else if (number % divisor == 0)
        false
      else
        isPrimeInternal(divisor + increment, 6 - increment)
    }

    isPrimeInternal(5, 2)
  }
}

def generatePrimeNumbers(count: Int): List[Int] = {
  @tailrec def generatePrimeNumbersInternal(number: Int = 3, index: Int = 0,
                                            primeNumbers: List[Int] = List(2)): List[Int] = {
    if (index == count)
      primeNumbers
    else if (isPrime(number))
      generatePrimeNumbersInternal(number + 2, index + 1, primeNumbers :+ number)
    else
      generatePrimeNumbersInternal(number + 2, index, primeNumbers)
  }

  generatePrimeNumbersInternal();
}

val primes = Stream.cons(2, Stream.from(3, 2) filter {isPrime(_)})

def calculateDivisors(number: Int) = {
  for {
    divisor &lt;- 1 to number
    if (number % divisor == 0)
  } yield divisor
}

@inline def decomposeToPrimeNumbers(number: Int) = {
  val sqrtOfNumber = math.sqrt(number).toInt

  @tailrec def decomposeToPrimeNumbersInternal(number: Int, primeNumberIndex: Int = 0,
                                               factors: List[Int] = List.empty[Int]): List[Int] = {
    val primeNumber = primes(primeNumberIndex)

    if (primeNumberIndex > sqrtOfNumber)
      factors
    else if (number % primeNumber == 0)
      decomposeToPrimeNumbersInternal(number / primeNumber, primeNumberIndex, factors :+ primeNumber)
    else
      decomposeToPrimeNumbersInternal(number, primeNumberIndex + 1, factors)
  }

  decomposeToPrimeNumbersInternal(number) groupBy {n => n} map {case (n: Int, l: List[Int]) => (n, l size)}
}

@inline def calculateNumberOfDivisors(number: Int) = {
  decomposeToPrimeNumbers(number) map {case (primeNumber, exponent) => exponent + 1} product
}

@tailrec def calculate(number: Int = 12300): Int = {
  val triangleNumber = ((number * number) + number) / 2
  val startTime = System.currentTimeMillis()
  val numberOfDivisors = calculateNumberOfDivisors(triangleNumber)
  val elapsedTime = System.currentTimeMillis() - startTime

  printf("%d: V: %d D: %d T: %dms\n", number, triangleNumber, numberOfDivisors, elapsedTime)

  if (numberOfDivisors > 500)
    triangleNumber
  else
    calculate(number + 1)
}

println(calculate())

Answer 1

, . , , . n n 5 sqrt(n), 2 3. , , , , , . . Scala .

, , .

, Stream . , Stream, Array. if .

  @tailrec def decomposeToPrimeNumbersInternal(number: Int, primes: Stream[Int],
                                               factors: List[Int] = List.empty[Int]): List[Int] = {
    val primeNumber = primes.head

    // Comparing primeNumberIndex with sqrtOfNumber didn't make any sense
    if (primeNumber > sqrtOfNumber) 
      factors
    else if (number % primeNumber == 0)
      decomposeToPrimeNumbersInternal(number / primeNumber, primes, factors :+ primeNumber)
    else
      decomposeToPrimeNumbersInternal(number, primes.tail, factors)
  }

Answer 2

....? , Scala, ?

, , . isPrimeInternal , .

Answer 3

, , . , , - /, . , , , Stream - , isPrime, 2,3- (1 5 mod 6) . , ,

def isPrime(number: Int): Boolean = {
  val sq = math.sqrt(number + 0.5).toInt
  ! primes.takeWhile(_ <= sq).exists(p => number % p == 0)
}

Answer 4

My scala , . 12.

def countDivisors (numberToFindDivisor: BigInt): Int = {

def countWithAcc(numberToFindDivisor: BigInt, currentCandidate: Int, currentCountOfDivisors: Int,limit: BigInt): Int = {

  if (currentCandidate >= limit) currentCountOfDivisors

  else {

    if (numberToFindDivisor % currentCandidate == 0)

      countWithAcc(numberToFindDivisor, currentCandidate + 1, currentCountOfDivisors + 2, numberToFindDivisor / currentCandidate)

    else

      countWithAcc(numberToFindDivisor, currentCandidate + 1, currentCountOfDivisors, limit)

  }

}

countWithAcc(numberToFindDivisor, 1, 0, numberToFindDivisor + 1)

}

Answer 5

calculateDivisors can be significantly improved only by checking the divisors of the square root of a number. Each time you find the divisor below sqrt, you will also find the one above.

def calculateDivisors(n: Int) = {
  var res = 1
  val intSqrt = Math.sqrt(n).toInt
  for (i <- 2 until intSqrt) {
      if (n % i == 0) {
          res += 2
      }
  }
  if (n == intSqrt * intSqrt) {
      res += 1
  }
  res
}