检查一个数是否为 Scala 中的质数

1. Introduction

In this tutorial, we’ll learn various methods to check if a number is prime in Scala.

2. Solutions

A prime number has no divisors other than 1 and itself. Non-prime numbers are called composite. 1 is neither prime nor composite. Additionally, negative numbers aren’t considered as prime numbers.

In this section, let’s look at different ways to check if a number is prime or not.

2.1. Idiomatic Scala Implementation

Let’s implement the prime check algorithm using idiomatic Scala. We can utilize the forAll() method on Range to check if there is any divisor for the input number:

def isPrimeSimple(num: Long): Boolean = {
  if (num <= 1) false
  else if (num == 2 || num == 3) true
  else
    (2L to num / 2).forall(num % _ != 0)
}

This approach is effective for smaller numbers, however its performance deteriorates with larger numbers.

Utilizing the property of factors, we can optimize this code by iterating only up to the square root of the input number instead of n/2. This improves the performance compared to our previous solution:

def isPrime(num: Long): Boolean = {
  if (num <= 1) false
  else if (num == 2 || num == 3) true
  else
    (2L to Math.sqrt(num).toLong).forall(num % _ != 0)
}

Nevertheless, this method experiences performance degradation with larger numbers, as it still needs to iterate over a substantial number of elements. We can still optimize the algorithm by using the 6k+-1 property of prime numbers:

def isPrimeOptimized(num: Long): Boolean = {
  if (num < 2) false
  else if (num == 2 || num == 3) true
  else if (num % 2 == 0 || num % 3 == 0) false
  else
    (5 to Math.sqrt(num).toInt by 6).forall(n =>
      num % n != 0 && num % (n + 2) != 0
    )
}

This significantly improves the performance of the algorithm by reducing the number of factors to check.

Nonetheless, for very high numbers, this method might still be non-performant.

2.2. Using BigInt

In the previous section, we implemented custom checks for prime numbers. As mentioned, its performance deteriorates as the number becomes very large.

Fortunately, alternative algorithms, such as the Miller Rabin test, perform more efficiently on bigger numbers. The BigInt class in the standard library provides an implementation of the same. We can utilize the method isProbablePrime() to check if a number is probably prime:

def isPrimeUsingBigInt(num: Long): Boolean = {
  if (num < 0) false
  else
    BigInt(num).isProbablePrime(certainty = 100)
}

The method isProbablyPrime() takes a probability value that is used by the algorithm to determine the number of iterations for the primality verification. We should be aware that using a high certainty value may lead to longer calculation times for the method.

Additionally, we check if the number is negative since the isProbablePrime() method takes the absolute value of the input. According to our assumptions, we consider negative numbers as non-prime.

3. Conclusion

In this article, we looked at different implementations of checking if a number is prime or not. We explored custom implementation as well as the more efficient one provided by the standard library.

As always, the sample code used in this tutorial is available over on GitHub.