Recursion in a prime generator

Question

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

see this answer http://stackoverflow.com/questions/3789968/generate-a-list-of-primes-in-r-up-to-a-certain-number/3791284#3791284 — John, Oct 05 '10 at 04:08
you would also want to cut out even numbers in `x` and periodically grow the size of `a` rather than with each addition to improve speed. — James, Oct 05 '10 at 09:20

Wine · Answer 1 · 2010-10-04T21:01:13.980

3

The solution might be to cut out the second loop and instead compare your proposed prime number to the entire vector instead, like:

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

That seemed to work for me.

edited Oct 04 '10 at 21:01

answered Oct 04 '10 at 20:50

Wine

246
1
3

score 1 · Accepted Answer · edited May 23 '17 at 11:48

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
}

(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.)

Recursion in a prime generator

2 Answers2

Linked