有没有更有效的方法来使用递归函数检查数字是否为质数？

Question

我正在编写一个递归函数来检查 SCALA 中非负整数是否为素数。我的函数需要两个输入来执行此操作。这是我的代码：

import io.StdIn._
def isPrime (x:Int, i:Int): Boolean = {
  if (i < 3) {
    true
  }else if (x % i == 0) {
    false
  }else{
    isPrime(x,i-1)
  }
}

print("Enter a number to check if it is a prime number: " )
val num1 = readInt()
println(isPrime(num1,num1-1))

我的问题是，有没有办法让我将一个输入作为函数的参数？代码必须使用递归函数。我知道有更有效的方法来检查一个数是否为素数（也许使用迭代），但我只是将其作为练习题来做。

Answer 1

用调用函数包装递归函数是完全没问题的，即使是标准做法。例如：

def isPrime( x:Int ) = { 
  def recIsP( n:Int, i:Int ) : Boolean = i == n || n % i != 0 && recIsP(n, i + 1) 
  recIsP(x,2) 
}

isPrime(3301)

Answer 2

一个选择是创建一个内部方法

def isPrime(x:Int): Boolean = {
  def loop(i: Int): Boolean = 
    if (i<3 ) {
      true
    } else if (x % i==0) {
      false
    } else {
      isPrime(x,i-1)
    }
  loop(x, x - 1)
}

另一种选择是设置默认参数。那些不能引用以前的参数，所以你必须使用一个变通方法。在这里，我传递了一些 j，并制作了 i = x - j，所以我可以从 1

开始递增 j

def isPrime(x: Int, j: Int = 1): Boolean = {
  val i = x - j
  if (i < 3) {
    true
  } else if (x % i==0) {
    false
  } else {
    isPrime(x, j + 1)
  }
}

与此无关，您的代码中存在错误：4 不应该是素数。

有没有更有效的方法来使用递归函数检查数字是否为质数？

Is there a more effective way to check if a number is prime using recursive function?

recursion

primes

scala