RcppAlgos (version 0.2.1)

primeSieve: Generate Prime Integers

Description

Rcpp implementation of the sieve of Eratosthenes. Generates all prime numbers between bound1 and bound2 (if supplied) or all primes up to bound1.

Usage

primeSieve(bound1 = 100L, bound2 = NULL)

Arguments

bound1

Positive integer or numeric value.

bound2

Positive integer or numeric value.

Value

Returns an integer vector if only bound1 is provided, otherwise a numeric vector is returned.

Details

Optimized implementation of the sieve of Eratosthenes. In addition to being very fast, this algorithm is particularly memory efficient when the sieving interval isn't large (E.g. check object.size when abs(bound1 - bound2) < 10^5). This is accomplished by doing most of the work with logical vectors and only allocating enough memory for the return vector based off of the size of the interval.

References

Sieve of Eratosthenes, 53-bit significand precision

See Also

Primes

Examples

# NOT RUN {
## Primes up to a thousand
primeSieve(1000)

## Primes between 42 and 1729
primeSieve(42, 1729)

## Equivalent to 
primeSieve(1729, 42)

## Primes up to one hundred million in no time
system.time(primeSieve(10^8))

options(scipen = 50)
## Quickly generate large primes over small interval
system.time(myPs <- primeSieve(10^13+10^5, 10^13))
## Object created is small
object.size(myPs)

## Different classes when bound2 is provided
class(primeSieve(10^4))
class(primeSieve(1, 10^4))
all.equal(primeSieve(1,10^4), primeSieve(10^4))

## Compared to generating all primes up to the 
## upper bound and subsetting (see below)
system.time(bound2_used <- primeSieve(10^9, 10^9+10^3))
object.size(bound2_used)

# }
# NOT RUN {
## Takes a decent amount of time
system.time(bound2_notused <- primeSieve(1000001000))
system.time(bound2_notused[bound2_notused >= 10^9])
## Creates large object
object.size(bound2_notused)
all.equal(bound2_notused[bound2_notused >= 10^9], bound2_used)
# }