RcppAlgos (version 0.2.1)

eulerPhiSieve: Number of Coprime Integers for all Integers up to \(n\)

Description

Rcpp sieve implementation that quickly generates the number of coprime integers up to \(n\). This is equivalent to performing Euler's phi function on every number up to \(n\).

Usage

eulerPhiSieve(n = 100L)

Arguments

n

Positive integer or numeric value.

Value

Returns an integer vector

Details

This function first generates all primes up to \(n\) via the sieve of Eratosthenes. Subsequently we use these primes to sieve over the sequence 1:n, multiplying each index by \((1 - 1/p)\) for each \(p\). Finally, we coerce the resulting elements to integers as the intermediate results are not integer types.

This function is very useful when you need to calculate Euler's phi function on many numbers as performing this calculation on the fly can be computationally expensive.

References

Euler's totient function

See Also

eulersPhi

Examples

# NOT RUN {
## Generate some random data
set.seed(496)
mySamp <- sample(10^6, 5*10^5)

## Quickly generate number of coprime elements for many numbers
system.time(myPhis <- eulerPhiSieve(10^6))

## Now use result in algorithm
for (s in mySamp) {
    sPhi <- myPhis[s]
    ## Continue algorithm
}

## See https://projecteuler.net
system.time(which.max((1:10^6)/eulerPhiSieve(10^6)))
# }