素数生成器中的递归

本文介绍了素数生成器中的递归的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在制作一个素数生成器，为了提高效率，我试图只针对我已经找到的素数而不是所有数字来测试数字<正在测试的数字的 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.)