素数生成器中的递归 [英] Recursion in a prime generator

问题描述

我正在制作一个素数生成器，为了提高效率，我试图只针对我已经找到的素数而不是所有数字来测试数字<正在测试的数字的 sqrt.我试图让 a 成为我的质数列表，但我不确定如何让它在我的第二个 for 循环中重复出现.我认为这只是针对 a <- 2 而不是 a <- c(a,i)

I'm making a prime generator, and to make it more efficient, i'm trying to only test numbers against primes that I've already found rather than all numbers < sqrt of the number being tested. I'm trying to get a to be my list of primes, but i'm not sure how to make it recur inside my second for loop. I think this is only testing against a <- 2 and not 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

推荐答案

下面是一个使用简单素数函数的非递归 mod，它的速度与您在 R 中的速度差不多.它不是遍历每个单独的值并测试它的素数，而是删除大块中的所有素数倍数.这将每个后续剩余值隔离为素数.所以，它取出 2x，然后 3x，然后 4 消失，所以 5x 值消失.这是在 R 中最有效的方法.

A non-recursive mod using simple prime function that's about as fast as you can make it in R is below. Rather than cycle through each individual value and test it's primeness it removes all of the multiples of primes in big chunks. This isolates each subsequent remaining value as a prime. So, it takes out 2x, then 3x, then 4 is gone so 5x values go. It's the most efficient way to do it in 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 倍.)

(you might want to see this stack question for faster methods using a sieve and also my timings of the function. What's above will run 50, maybe 500x faster than the version you're working from.)

这篇关于素数生成器中的递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！