Checking whether a number is prime in Scala

Question

I wanted to check if a number is prime or not. I wrote the following code, but it does not return any value:

 def isprime(x:Int) = {
     | if (x==1) false
     | else {
     | for (i <- 2 to x-1) {
     | if (x % i == 0) false
     | else true
     | }
     | }
     | }

Answer 1

What you did is a called defining a function so obviously it won't return anything and as a matter of fact, this function returns AnyVal which obviously won't help you much. I suspect that you actually need a Boolean type returned.

Since you are working with the REPL, you would want to define your function to check if a number is prime. I called it isPrime2 and then test it.

def isPrime2(i :Int) : Boolean = {
|     if (i <= 1)
|       false
|     else if (i == 2)
|       true
|     else
|       !(2 to (i-1)).exists(x => i % x == 0)
|   }
// isPrime2: (i: Int)Boolean

(1 to 10).foreach(i => if (isPrime2(i)) println("%d is prime.".format(i)))
// 2 is prime.
// 3 is prime.
// 5 is prime.
// 7 is prime.

I would even suggest a simpler version if you care not using if else conditions :

def isPrime1(n: Int): Boolean = ! ((2 until n-1) exists (n % _ == 0))

Which also returns a Boolean.

EDIT:

As @TheArchetypalPaul stated, which was also implied, the problem is that your for loop isn't resulting in any value - you calculate a true/false value, but then don't do anything with it. So your else clause doesn't result in any value (in fact, it produces Unit). You need to return false as soon as you find a divisor - and the way to do that is probably exists as in isPrime1.

Answer 2

One liner Solution

def isPrime(num:Int):Boolean =
(num > 1) && !(2 to scala.math.sqrt(num).toInt).exists(x => num % x == 0)

Answer 3

Here is one more 1 line solution:

def isPrime(n: Int) = Range(2, n-1).filter(i => n % i == 0).length == 0 

Or even shorter:

def isPrime(n: Int) = Range(2, n-1).filter(n % _ == 0).length == 0

Answer 4

This one is less elegant than the one liners, but a bit faster. It uses the fact that all primes (except 2 and 3) have to be at 6k±1. So it skips testing numbers which are dividable by 2 or 3. It will only test for the groups of (5, 7), (11, 13), (17, 19) and so on.

def isPrime(number: Int): Boolean =
  if (number < 4) number > 1
  else if (number % 2 == 0 || number % 3 == 0) false
  else (5 to math.sqrt(number).toInt by 6).forall(i => number % i != 0 && number % (i + 2) != 0)

Answer 5

Here is another one liner:

def isPrime(num: Int): Boolean = (2 to num) forall (x => num % x != 0)

forall will check if the predicate holds for all elements of this range

I just realised that the code above is a bit slow for bigger numbers, so here an improved version:

def isPrime(n: Int): Boolean = (2 to math.sqrt(n).toInt) forall (x => n % x != 0)

Answer 6

Many of the solutions in the answers to this question appear to either not work, haven't covered obvious edge cases, and/or are blatantly inefficient.

Below is my answer which works, covers all edge cases, and is as efficient as it is possible to be in this particular domain; i.e. it checks as few values as possible and it fails early as possible if the number isn't a prime.

def isPrime(long: Long): Boolean =
  if (long > 8L) {
    !(((long % 2L) == 0L)
      || (3L to math.sqrt(long).toLong by 2L).exists(n => (long % n) == 0L))
  } else
    (long > 1L) && ((long == 2L) || ((long % 2L) != 0L))

UPDATE (2019/09/18): I stand corrected about my solution being "is as efficient as it is possible to be in this particular domain". The solution provided by @kanbagoly is actually more efficient in that it has fewer checks. His is implemented using Int. Here's his solution reimplemented using Long just in case you want to only do a copy/paste and not run into stupid Int versus Long issues:

def isPrime(long: Long): Boolean =
  if (long < 4L)
    long > 1L
  else if (((long % 2L) == 0L) || ((long % 3L) == 0L))
    false
  else
    (5L to math.sqrt(long).toLong by 6L)
      .forall(n => ((long % n) != 0L) && ((long % (n + 2L)) != 0L))

Answer 7

This can be a solutions.

def isPrime(integer: Int): Boolean = {
   if (integer == 1) false
   else {
      val domain = (2 to math.sqrt(integer).toInt).view
      val range = domain filter (isDivisibleBy(integer, _))
      range.isEmpty
   }
}

def isDivisibleBy(integer: Int, divisor: Int): Boolean = integer % divisor == 0

Now coming back to the code that you have written, your code returns AnyVal and desired return type should be Boolean. And the reason behind that is in Scala (or any functional language) for loop is an expression not a control structure.

Answer 8

Comment on the former answers (except @jwvh): there is no need to use even numbers more than once. After a test by 2, the domain 3 to math.sqrt(integer).toInt by 2 must be used.

I have developed an accelerated tail-recursive version. It skips even values, and test two values in one go.

See it for yourself, running in your browser Scastie (remote JVM).

import java.lang.System.currentTimeMillis

import scala.annotation.tailrec
import scala.collection.immutable.TreeSet
import scala.io.Source

// Primality by trial division

object PrimesTestery extends App {
  val oeisPrimes = TreeSet(oeisPrimesText.map(_.toInt): _*)

  def oeisPrimesText = rawText.getLines.takeWhile(_.nonEmpty).map(_.split(" ")(1)).toList

  def rawText = Source.fromURL("https://oeis.org/A000040/a000040.txt")

  def isPrime(n: Long) = {
    val end = math.sqrt(n.toDouble).toInt

    @tailrec
    def inner(d: Int): Boolean = {
      (d > end) || (n % d != 0 && n % (d + 2) != 0) && inner(d + 6)
    }

    n > 1 && ((n & 1) != 0 || n == 2) && (n % 3 != 0 || n == 3) && inner(5)
  }

  println(s"Found ${oeisPrimes.size} primes on OEIS , last is ${oeisPrimes.last}.")
  for (i <- (0 to oeisPrimes.last))
    assert(isPrime(i.toLong) == oeisPrimes.contains(i), s"Wrong $i")

  println(s"✔ Successfully completed without errors. [total ${currentTimeMillis - executionStart} ms]")

}

To be sure, this code test against the known list of primes for primes ánd composite numbers.

Answer 9

def isPrime(n: Int) = (2 until n) forall(x => n % x !=0)

Answer 10

also you can use this recursive function:

def isPrime(n: Int):Boolean = {
  def isPrimeUntil(t: Int): Boolean =
    if (t<=1) true
    else n%t != 0 && isPrimeUntil(t-1)

    isPrimeUntil(n/2)
}

Answer 11

That works fine for negative numbers and big numbers too. Prime numbers start from 2, 3, 5, ...

def isPrime(n: Int): Boolean = (n > 1) && ! Range(2, n-1).exists(n % _ == 0)

Also

@tailrec
def isPrime(n: Int): Boolean = {
   def isPrimeTailrec(divisor: Int): Boolean = {
     if(divisor > Math.sqrt(Math.abs(n))) true
       else n % divisor != 0 && isPrimeTailrec(divisor + 1)
     }
     if(n < 2) false
     else isPrimeTailrec(2)
   }
}

Answer 12

You can also use Wilson's theorem. p is prime if (p-1)! = -1 mod p. Normally computing (p-1)! is expensive as the number becomes huge, but computing the factorial mod p is less than p.

def prime(p):Boolean = {
  if (p==1)
    false
  else if (Seq(2,3,5,7,11).contains(p))
    false
  else
    // detect whether (p-1)! == -1 mod p
    (2 until p).fold(1)((acc:Int,i:Int) => (acc * i) % p) == p-1
}

Answer 13

def primeNumber(range: Int): Unit ={

val primeNumbers: immutable.IndexedSeq[AnyVal] =

  for (number :Int <- 2 to range) yield{

    val isPrime = !Range(2, Math.sqrt(number).toInt).exists(x => number % x == 0)

    if(isPrime)  number
  }

for(prime <- primeNumbers) println(prime)

}