Generate a list of primes up to a certain number

That sieve posted by George Dontas is a good starting point. Here's a much faster version with running times for 1e6 primes of 0.095s as opposed to 30s for the original version.

sieve <- function(n){   n <- as.integer(n)   if(n > 1e8) stop("n too large")   primes <- rep(TRUE, n)   primes[1] <- FALSE   last.prime <- 2L   fsqr <- floor(sqrt(n))   while (last.prime <= fsqr)   {      primes[seq.int(2L*last.prime, n, last.prime)] <- FALSE      sel <- which(primes[(last.prime+1):(fsqr+1)])      if(any(sel)){        last.prime <- last.prime + min(sel)      }else last.prime <- fsqr+1   }   which(primes)}

Here are some alternate algorithms below coded about as fast as possible in R. They are slower than the sieve but a heck of a lot faster than the questioners original post.

Here's a recursive function that uses mod but is vectorized. It returns for 1e5 almost instantaneously and 1e6 in under 2s.

primes <- function(n){    primesR <- function(p, i = 1){        f <- p %% p[i] == 0 & p != p[i]        if (any(f)){            p <- primesR(p[!f], i+1)        }        p    }    primesR(2:n)}

The next one isn't recursive and faster again. The code below does primes up to 1e6 in about 1.5s on my machine.

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}

BTW, the spuRs package has a number of prime finding functions including a sieve of E. Haven't checked to see what the speed is like for them.

And while I'm writing a very long answer... here's how you'd check in R if one value is prime.

isPrime <- function(x){    div <- 2:ceiling(sqrt(x))    !any(x %% div == 0)}

This is an implementation of the Sieve of Eratosthenes algorithm in R.

sieve <- function(n){   n <- as.integer(n)   if(n > 1e6) stop("n too large")   primes <- rep(TRUE, n)   primes[1] <- FALSE   last.prime <- 2L   for(i in last.prime:floor(sqrt(n)))   {      primes[seq.int(2L*last.prime, n, last.prime)] <- FALSE      last.prime <- last.prime + min(which(primes[(last.prime+1):n]))   }   which(primes)} sieve(1000000)

Best way that I know of to generate all primes (without getting into crazy math) is to use the Sieve of Eratosthenes.

It is pretty straightforward to implement and allows you calculate primes without using division or modulus. The only downside is that it is memory intensive, but various optimizations can be made to improve memory (ignoring all even numbers for instance).