Реализация функции для определения, является ли число простым с использованием any () в R

Question

Изучал способы избежать цикла for и вместо этого использовать функцию any () для реализации функции, которая дает истину, когда переданный аргумент является простым, а ложь другим.

Вот что у меня есть:

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 здесь неуместно в этой ситуации.Эта функция просто возвращает минимум и максимум данного вектора (см. ?range для получения дополнительной информации).Итак, для вашего примера 55, так как range(2:54) возвращает 2 и 54, 55 не делится ни на одно из этих чисел, следовательно, возвращение 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, и я настоятельно рекомендую узнать об этом. 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

Надеемся, вы увидите, что есть много фундаментальных понятий, которые можно убрать из этого простого упражнения.Если вы действительно хотите узнать о тестах на простоту, вам следует проверить тест на простоту Миллера-Рабина , который реализован в gmp, numbers и других пакетах.