How to iterate over a List of numbers and check if there are pairs of numbers that add up to a given-CodePudding

I have to generate a list of prime numbers smaller than a given number and then find all pairs of the generated prime numbers that add up to that value.

E.g. num = 12

smaller_primes = List(3, 5, 7, 11)

Desirable outcome: List((5, 7))

I had no problem with generating the list of smaller prime numbers, but I don't know how to check what pairs fulfill the requirement. This is what I tried:

def check_sum(n: Int) = 
    val get_primes = (List.range(2, n)).filter(num => check_prime_bool(num))  // generating list of smaller prime numbers
    val x = for {
        a <- get_primes
        b <- get_primes
        if a   b == n 
    } yield (a,b)
    x

This solution works but I can't use the for/yield construction, I can only use functions like map(), filter(), etc.

CodePudding user response：

The exact same implementation you have already implemented, but using map, ... would be:

def checkSum(n: Int) = {
  val getPrimes = ((2 to n).filter(check_prime_bool)
  getPrimes.flatMap { a => 
    getPrimes.map(b => (a, b)).filter(b => a   b == n)
  }
}

Take it like this, the first reverse arrow in the for comprehension is compiled into: getPrimes.flatMap { a => } (You're naming the variable for iteration as "a" inside your for comprehension). The second line of the for comprehension is compiled into: getPrimes.map { b => } (note the variable "b" name, it's just the same as you're passing). "if" is compiled into .withFilter method, you can use filter instead.

But if you wanted to, I can suggest another implementations which is tailrec and is O(n) instead of O(n^2) (It doesn't use map, flatMap, ..., if anyone can suggest a better implementation for this approach, you're welcome to edit this answer):

import scala.annotation.tailrec

// assuming primes are sorted (since (2 to n).filter(isPrime) which you're using in this case, is sorted)
@tailrec
def checkSum(primes: Array[Int], acc: List[(Int, Int)] = List.empty, leftIndex: Int = 0, rightIndex: Int, num: Int): List[(Int, Int)] = {
  if (leftIndex >= rightIndex) acc // pointers have reached each other, that's the end of the list
  else {
    val left = primes(leftIndex)
    val right = primes(rightIndex)
    val sum = left   right
    if (sum == num) checkSum(primes, (left -> right)  : acc, leftIndex   1, rightIndex - 1, num)
    else if (sum < num) { // move left pointer to right
      checkSum(primes, acc, leftIndex   1, rightIndex, num)
    } else { // move right pointer to left
      checkSum(primes, acc, leftIndex, rightIndex - 1, num)
    }
  }
}

val primeNumbers = (2 to 12).filter(isPrime).toArray
checkSum(primeNumbers, rightIndex = primeNumbers.length - 1, num = 12) 
// => List[(5, 7)]