Find next prime

Question

I wrote small app finding next prime number starting from number passed as argument:

object HelloWorld extends App {

    println(findNextPrime(49));

    def findNextPrime(n: Int) : Int = {
        var m = n;
        while(true){
           m += 1;
           if(isPrime(m)){
               return m;
           }
       }
       throw new Exception("Something went wrong.");
    }

    def isPrime(n: Int): Boolean = {
        n match {
            case 0|1 => return false
            case 2|3 => return true
            case _ => { 
                (2 to Math.sqrt(n).toInt).forall(y => n%y!=0)
            }
        }
    }
}

Is there better (more functional way) to wrote findNextPrime in Scala ?

Answer 1

Avoid mutation where possible

In Scala and functional programming as such mutating the state should be avoided

In you case you can use simple recursion and inner function

def findNextPrime(n: Int) : Int = {
  def iterate(m: Int) : Int ={
    if(isPrime(m)) m
    else iterate(m +1)
  }
  iterate(n)
}

Little things

You dont need closing brackets if pattern matching is the only thing in the function

You don't need to use ; characters in scala. Same goes for return statements

  def isPrime(n: Int): Boolean = n match {
    case 0|1 => false
    case 2|3 => true
    case _ => {
      (2 to Math.sqrt(n).toInt).forall(y => n%y!=0)
    }
  }

Answer 2

With the exception of the number 2, the next prime number will not be 1 away from the number that you have entered, so this can be amended:

m += 1;

to something like:

if(m == 2){
    m += 1;
}else if(m >= 3 && m%2 == 1){
    m += 2;
}else if(m >= 3 && m%2 == 0){
    m += 1;
}else{
    // Number is not prime
}

I'm not sure about the exact Scala syntax, nor do I know the probability of the next prime number being n+2, but this will reduce the number of calls to your isPrime() method which will make your program more efficient.

I've corrected the logic to account for positive even numbers been entered. Once it hits an odd number then it will add 2. This will need testing and debugging. The m%2 is modulo in C and C-based languages; not sure if this is correct for Scala.

Answer 3

Is there a better way? Sure. I kinda like this way

def findNextPrime(n: Int): Int = n match {
    case simp if n < 2 => 2
    case _ => Stream.from(n + 1).dropWhile {
        p => 2 +: (3 to Math.sqrt(p).toInt by 2) exists (p % _ == 0)
    }.head
}