Рекурсия в простом генераторе

Question

Я делаю простой генератор и, чтобы сделать его более эффективным, я пытаюсь проверять только числа по найденным мною простым числам, а не по всем числам a <- 2, а не a <- c(a,i)

x <- 3:1000
a <- 2
for (i in x)
 {for (j in a)
  {if (i %% j == 0)
   {next}
  else {a <- unique(c(a,i))}}}
a

Answer 1

Решение может заключаться в том, чтобы вырезать второй цикл и вместо этого сравнить предложенное простое число со всем вектором, например:

x <- 3:1000
a <- 2
for (i in x) {
  if (!any(i %% a == 0)) {
    a <- c(a,i)
  }
}

Это, похоже, работает для меня.

Answer 2

Нерекурсивный мод, использующий простую простую функцию, примерно такой же быстрый, как вы можете сделать это в R, ниже.Вместо того, чтобы перебирать каждое отдельное значение и проверять его простоту, он удаляет все кратные простых чисел в больших кусках.Это изолирует каждое последующее оставшееся значение как простое число.Таким образом, он принимает 2x, затем 3x, затем 4 исчезает, поэтому значения 5x уходят.Это наиболее эффективный способ сделать это в R.

primest <- function(n){
    p <- 2:n
    i <- 1
    while (p[i] <= sqrt(n)) {
        p <-  p[p %% p[i] != 0 | p==p[i]]
        i <- i+1
    }
    p
}

(вы можете захотеть увидеть этот вопрос о стеке для более быстрых методов, использующих сито, а также мои временные характеристики функции.выше будет работать 50, может быть, в 500 раз быстрее, чем версия, с которой вы работаете.)