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

Question

Я делаю генератор первичных чисел, и чтобы сделать его более эффективным, я пытаюсь только проверить числа против простых чисел, которые я уже нашел, а не все числа < sqrt проверяемого числа , Я пытаюсь получить мой список простых чисел, но я не уверен, как заставить его повториться в моем втором цикле. Я думаю, что это только испытание против 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

Рекурсивный мод с использованием простой простой функции, которая примерно так же быстро, как вы можете сделать это в 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 
} 

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

Answer 2

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

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

Казалось, это сработало для меня.