使用 R 中的 any() 实现检测数字是否为质数的函数

Question

正在探索避免 for 循环的方法，而是使用 any() 函数来实现一个函数，该函数在传递的参数为质数时给出 true，否则给出 false。

这是我的资料：

prime2 <- function(n) {
  rangeOfNumbers <- range(2:(n-1))
  if(any(n%%rangeOfNumbers == 0)){
    return(FALSE)
  }
  else return(TRUE)
}

看起来很直接，但是 prime(55) 给出 TRUE 而不是 false。

我做错了什么？

Answer 1

正如您所说，我们可以很容易地从许多包中调用一个 isprime 函数来快速获得您的答案，但这不是您的目标。您正在学习并试图理解 R 和一般编程的基本原理。很多荣誉！！

正如许多人指出的那样，在这种情况下使用 range 是不合适的。此函数只是 return 给定向量的最小值和最大值（有关详细信息，请参阅 ?range）。因此，对于您的 55 示例，由于 range(2:54) returns 2 和 54，55 不能被这些数字中的任何一个整除，因此 return TRUE.

如@LAP 所述，您需要冒号 : 运算符。因此，如果您将 range(2:(n-1)) 更改为简单的 2:(n-1)，您的算法将起作用（在大多数情况下......它不适用于 n <= 2）。

既然你说你在学习的过程中，你也应该以更有效和更周到的方式思考编码方式。为了检查一个数是否为质数，我们只需要检查到 n 的平方根。这将减少许多检查。

让我们再仔细想想如何避免进一步检查。我们知道在检查素数时，我们只需要考虑素数。由于 2 是唯一的偶数素数，我们可以首先检查输入是否为偶数，如果不是，则仅检查奇数的整除性。我们可以通过调用函数 seq 或 seq.int.

生成具有固定步骤的序列来实现最后一位

让我们看看实际效果：

## Pseudo-Corrected OP function (2 should return TRUE, 1 should return FALSE, etc.)
prime2 <- function(n) {
    rangeOfNumbers <- 2:(n-1)
    if(any(n%%rangeOfNumbers == 0)){
        return(FALSE)
    }
    else return(TRUE)
}

prime2Enhanced <- function(n) {
    if (n < 2)
        return(FALSE)
    else if (n %in% c(2, 3, 5, 7))
        return(TRUE)
    else if (n %% 2 == 0)
        return(FALSE)
    else if (any(n %% seq.int(3, sqrt(n), 2) == 0))
        return(FALSE)
    else
        return(TRUE)
}

all.equal(sapply(3:1000, prime2), as.logical(gmp::isprime(3:1000)))
[1] TRUE

all.equal(sapply(3:1000, prime2Enhanced), as.logical(gmp::isprime(3:1000)))
[1] TRUE

我们可以通过将我们的编程概念扩展到矢量化来做得更好。这是我们可以传递一个向量并一次获得所有结果而不是使用循环的时候。这是 R 中一个非常重要的概念，我强烈建议您了解它。 The R Inferno 是此类主题的极好资源（参见第 3 圈）。

prime2Vectorized <- function(v) {
    result <- rep(TRUE, length(v))
    testVec <- as.integer(c(2, seq(3, sqrt(max(v)), 2)))

    ## Although we are using a loop here, we are taking
    ## advantage of vectorization concepts with each x
    for (x in testVec) {
        s <- which(v >= x^2)
        result[s[v[s] %% x == 0]] <- FALSE
    }

    result
}

all.equal(prime2Vectorized(3:1000), as.logical(gmp::isprime(3:1000)))
[1] TRUE

我会将其保存为练习，以处理边缘情况和进一步优化。

现在，让我们看看我们在使用库的效率方面有多少改进 microbenchmark:

library(microbenchmark)
microbenchmark(orig = sapply(3:1000, prime2),
                 improved = sapply(3:1000, prime2Enhanced),
                 vectorize = prime2Vectorized(3:1000))
Unit: microseconds
     expr      min        lq      mean    median       uq       max neval
     orig 3863.279 4198.5595 5470.2178 4403.5050 4723.485 15775.377   100
 improved 1670.418 1740.1240 1937.2396 1809.6680 1935.365  9912.629   100
vectorize  202.006  218.5505  306.4068  233.9045  249.696  6243.121   100

希望您能从这个简单的练习中学到很多基本概念。如果你真的想了解素数测试，你应该查看 Miller-Rabin primality test，它在 gmp、numbers 和其他包中实现。

使用 R 中的 any() 实现检测数字是否为质数的函数

Implementing function to detect if a number is prime using any() in R

primes

r

data-analysis

any