R中的素数功能

Question

我正在尝试创建一个函数来测试给定的整数是否为素数,我尝试使用以下代码:

tpn <- function(prime.num){

    if(prime.num==2){
        print("PRIME")
    } else {

    if(prime.num%%(2:(prime.num-1))!=0){
        print("PRIME")

    } else { 
        print("NOT PRIME")

}}}

这不起作用,虽然我不明白为什么.我正在检查给定的数字是否可以被任何整数除以这个数字而没有余数.如果它不能,那么这个数字是素数.

我发现的另一个解决方案是

tpn <- function(pn){

    if(sum(pn/1:pn==pn%/%1:pn)==2)
            print("prime")

}

这有效.虽然,我无法理解sum(pn/1:pn == pn%/%1:pn) == 2实际测试的内容.

Answer 1

如果除法的结果等于整数除法的结果,则数字a可以被数字整除.任何整数都可以除以至少两个数字:和.素数是那些只能被这两者分开的数字.打破代码:ba / ba %/% bpn1pn

1. pn / 1:pn是的划分结果通过1,2...,pn
2. pn %/% 1:pn是整数除法的结果通过1,2...,pn
3. sum(pn / 1:pn == pn %/% 1:pn)是多少这些是相等的,即整数除数的数量pn.如果这个数字是2,你有一个素数.

您的代码出了什么问题:if需要测试某些内容是否存在,TRUE或者FALSE您是否将整个向量传递给它.而且,你的逻辑错了.应该是:

is.prime <- function(num) {
   if (num == 2) {
      TRUE
   } else if (any(num %% 2:(num-1) == 0)) {
      FALSE
   } else { 
      TRUE
   }
}

一旦你决定返回逻辑,你就可以缩短你的代码:

is.prime <- function(n) n == 2L || all(n %% 2L:max(2,floor(sqrt(n))) != 0)

(其中包含@ Carl关于不检查所有数字的评论.)

Answer 2

我刚刚尝试了is.prime代码示例.但是这个3不是素数; o)

改进版本使用天花板而不是地板操作.

is.prime <- function(n) n == 2L || all(n %% 2L:ceiling(sqrt(n)) != 0)

最好!

Answer 3

您也可以使用matlab包中的isprime()函数。它也适用于向量参数：

library(matlab)

as.logical(isprime(7))
as.logical(isprime(42))

#> as.logical(isprime(7))
#[1] TRUE
#> as.logical(isprime(42))
#[1] FALSE

Answer 4

查找素数的正则表达式

is.prime <- function(x) {
  x <- abs(as.integer(x))
  !grepl('^1?$|^(11+?)\\1+$', strrep('1', x))
}

(-100:100)[is.prime(-100:100)]
# [1]  -97 -89 -83 -79 -73 -71 -67 -61 -59 -53 -47 -43 -41 -37 -31 -29 -23 -19 -17 -13 -11  -7  -5  -3  -2
# [26]   2   3   5   7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97

http://diswww.mit.edu/bloom-picayune.mit.edu/perl/10138

或者，如果你取从 1 到 的所有整数x，则除以没有余数的数应该是 2:1 和x

is.prime <- function(x)
  vapply(x, function(y) sum(y / 1:y == y %/% 1:y), integer(1L)) == 2L

(1:100)[is.prime(1:100)]
# [1]  2  3  5  7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

我知道正则表达式会最慢，但它仍然是我的最爱

is.prime <- function(x)
  vapply(x, function(y) sum(y / 1:y == y %/% 1:y), integer(1L)) == 2L

is.prime_regex <- function(x) {
  x <- abs(as.integer(x))
  !grepl('^1?$|^(11+?)\\1+$', strrep('1', x))
}

is.prime_Seily  <- function(n)
  vapply(n, function(y)
    y == 2L || all(y %% 2L:ceiling(sqrt(y)) != 0), logical(1L))

is.prime_flodel <- function(n)
  vapply(n, function(y)
    y == 2L || all(y %% 2L:max(2,floor(sqrt(y))) != 0), logical(1L))

x <- 1:1000

library('microbenchmark')
microbenchmark(
  is.prime(x),
  is.prime_regex(x),
  is.prime_Seily(x),
  is.prime_flodel(x),
  unit = 'relative'
)

# Unit: relative
#               expr       min        lq      mean    median        uq        max neval cld
#        is.prime(x)  8.593971  8.606353  8.805690  8.892905  9.724452 21.9886734   100  b 
#  is.prime_regex(x) 84.572928 86.200415 76.413036 86.895956 85.117796 25.7106323   100   c
#  is.prime_Seily(x)  1.000000  1.000000  1.000000  1.000000  1.000000  1.0000000   100 a  
# is.prime_flodel(x)  1.146212  1.147971  1.144839  1.146119  1.163302  0.9085948   100 a