| Title: | Fast Functions for Prime Numbers |
|---|---|
| Description: | Fast functions for dealing with prime numbers, such as testing whether a number is prime and generating a sequence prime numbers. Additional functions include finding prime factors and Ruth-Aaron pairs, finding next and previous prime numbers in the series, finding or estimating the nth prime, estimating the number of primes less than or equal to an arbitrary number, computing primorials, prime k-tuples (e.g., twin primes), finding the greatest common divisor and smallest (least) common multiple, testing whether two numbers are coprime, and computing Euler's totient function. Most functions are vectorized for speed and convenience. |
| Authors: | Os Keyes [aut, cre],
Paul Egeler [aut] |
| Maintainer: | Os Keyes <[email protected]> |
| License: | MIT + file LICENSE |
| Version: | 1.6.0 |
| Built: | 2024-09-12 04:41:34 UTC |
| Source: | https://github.com/ironholds/primes |
These functions provide vectorized computations for the greatest common
divisor (gcd), smallest common multiple (scm), and coprimality. Coprime
numbers are also called mutually prime or relatively prime numbers.
The smallest common multiple is often called the least common multiple.
gcd(m, n) scm(m, n) coprime(m, n) Rgcd(...) Rscm(...)gcd(m, n) scm(m, n) coprime(m, n) Rgcd(...) Rscm(...)
m, n, ...
|
integer vectors. |
The greatest common divisor uses Euclid's algorithm, a fast and widely
used method. The smallest common multiple and coprimality are computed using
the gcd, where
and two numbers are coprime when .
The gcd, scm, and coprime functions perform element-wise computation.
The Rgcd and Rscm functions perform gcd and scm over multiple values
using reduction. That is, they compute the greatest common divisor and least
common multiple for an arbitrary number of integers based on the properties
and
. The binary
operation is applied to two elements; then the result is used as the first
operand in a call with the next element. This is done iteratively until all
elements are used. It is idiomatically equivalent to Reduce(gcd, x) or
Reduce(scm, x), where x is a vector of integers, but much faster.
The functions gcd, scm, and coprime return a vector of the
length of longest input vector. If one vector is shorter, it will be
recycled. The gcd and scm functions return an integer vector while
coprime returns a logical vector. The reduction functions Rgcd and
Rscm return a single integer.
Paul Egeler, MS
gcd(c(18, 22, 49, 13), 42) ## [1] 6 2 7 1 Rgcd(18, 24, 36, 12) ## [1] 6 scm(60, 90) ## [1] 180 Rscm(1:10) ## [1] 2520 coprime(60, c(77, 90)) ## [1] TRUE FALSEgcd(c(18, 22, 49, 13), 42) ## [1] 6 2 7 1 Rgcd(18, 24, 36, 12) ## [1] 6 scm(60, 90) ## [1] 180 Rscm(1:10) ## [1] 2520 coprime(60, c(77, 90)) ## [1] TRUE FALSE
Generate a sequence of prime numbers from min to max or generate a vector
of the first n primes. Both functions use a fast implementation of the
Sieve of Eratosthenes.
generate_n_primes(n) generate_primes(min = 2L, max)generate_n_primes(n) generate_primes(min = 2L, max)
n |
the number of primes to generate. |
min |
the lower bound of the sequence. |
max |
the upper bound of the sequence. |
An integer vector of prime numbers.
Paul Egeler, MS
generate_primes(max = 12) ## [1] 2 3 5 7 11 generate_n_primes(5) ## [1] 2 3 5 7 11generate_primes(max = 12) ## [1] 2 3 5 7 11 generate_n_primes(5) ## [1] 2 3 5 7 11
Test whether a vector of numbers is prime or composite.
is_prime(x)is_prime(x)
x |
an integer vector containing elements to be tested for primality. |
A logical vector.
Os Keyes and Paul Egeler, MS
is_prime(4:7) ## [1] FALSE TRUE FALSE TRUE is_prime(1299827) ## [1] TRUEis_prime(4:7) ## [1] FALSE TRUE FALSE TRUE is_prime(1299827) ## [1] TRUE
Use prime k-tuples to create lists of twin primes, cousin primes, prime triplets, and so forth.
k_tuple(min, max, tuple) sexy_prime_triplets(min, max) twin_primes(min, max) cousin_primes(min, max) sexy_primes(min, max) third_cousin_primes(min, max)k_tuple(min, max, tuple) sexy_prime_triplets(min, max) twin_primes(min, max) cousin_primes(min, max) sexy_primes(min, max) third_cousin_primes(min, max)
min |
the lower bound of the sequence. |
max |
the upper bound of the sequence. |
tuple |
an integer vector representing the target k-tuple pattern. |
You can construct your own tuples and generate series of primes using
k_tuple; however, there are functions that exist for some of the named
relationships. They are listed below.
twin_primes: represents c(0,2).
cousin_primes: represents c(0,4).
third_cousin_primes: represents c(0,8).
sexy_primes: represents c(0,6).
sexy_prime_triplets: represents c(0,6,12). (This relationship is
unique in that is guaranteed to be composite.)
The term "third cousin primes" is of the author's coinage. There is no canonical name for that relationship to the author's knowledge.
A list of vectors of prime numbers satisfying the condition of
tuple.
Paul Egeler, MS
# All twin primes up to 13 twin_primes(2, 13) # Identical to `k_tuple(2, 13, c(0,2))` ## [[1]] ## [1] 3 5 ## ## [[2]] ## [1] 5 7 ## ## [[3]] ## [1] 11 13 # Some prime triplets k_tuple(2, 19, c(0,4,6)) ## [[1]] ## [1] 7 11 13 ## ## [[2]] ## [1] 13 17 19# All twin primes up to 13 twin_primes(2, 13) # Identical to `k_tuple(2, 13, c(0,2))` ## [[1]] ## [1] 3 5 ## ## [[2]] ## [1] 5 7 ## ## [[3]] ## [1] 11 13 # Some prime triplets k_tuple(2, 19, c(0,4,6)) ## [[1]] ## [1] 7 11 13 ## ## [[2]] ## [1] 13 17 19
Find the next prime numbers or previous prime numbers over a vector.
next_prime(x) prev_prime(x)next_prime(x) prev_prime(x)
x |
a vector of integers from which to start the search. |
For prev_prime, if a value is less than or equal to 2, the function will
return NA.
An integer vector of prime numbers.
Paul Egeler, MS
next_prime(5) ## [1] 7 prev_prime(5:7) ## [1] 3 5 5next_prime(5) ## [1] 7 prev_prime(5:7) ## [1] 3 5 5
Get the n-th prime, , in the sequence of primes.
nth_prime(x)nth_prime(x)
x |
an integer vector. |
An integer vector.
Paul Egeler, MS
nth_prime(5) ## [1] 11 nth_prime(c(1:3, 7)) ## [1] 2 3 5 17nth_prime(5) ## [1] 11 nth_prime(c(1:3, 7)) ## [1] 2 3 5 17
Compute Euler's Totient Function (). Provides the
count of integers that are coprime with such that
and .
phi(n)phi(n)
n |
an integer vector. |
An integer vector.
Paul Egeler, MS
"Euler's totient function" (2020) Wikipedia. https://en.wikipedia.org/wiki/Euler%27s_totient_function (Accessed 21 Aug 2020).
phi(12) ## [1] 4 phi(c(9, 10, 142)) ## [1] 6 4 70phi(12) ## [1] 4 phi(c(9, 10, 142)) ## [1] 6 4 70
Functions for estimating —the number of primes less than
or equal to —and for estimating the value of , the n-th
prime number.
prime_count(n, upper_bound) nth_prime_estimate(n, upper_bound)prime_count(n, upper_bound) nth_prime_estimate(n, upper_bound)
n |
an integer. See Details for more information. |
upper_bound |
a logical indicating whether to estimate the lower- or upper bound. |
The prime_count function estimates the number of primes .
When upper_bound = FALSE, it is guaranteed to under-estimate for all
.
When upper_bound = TRUE, it holds for all positive .
The nth_prime_estimate function brackets upper and lower bound values of
the nth prime. It is valid for .
The methods of estimation used here are a few of many alternatives. For further information, the reader is directed to the References section.
Paul Egeler, MS
"Prime-counting function" (2020) Wikipedia. https://en.wikipedia.org/wiki/Prime-counting_function#Inequalities (Accessed 26 Jul 2020).
Compute the prime factors of elements of an integer vector.
prime_factors(x)prime_factors(x)
x |
an integer vector. |
A list of integer vectors reflecting the prime factorizations of each element of the input vector.
Paul Egeler, MS
prime_factors(c(1, 5:7, 99)) ## [[1]] ## integer(0) ## ## [[2]] ## [1] 5 ## ## [[3]] ## [1] 2 3 ## ## [[4]] ## [1] 7 ## ## [[5]] ## [1] 3 3 11prime_factors(c(1, 5:7, 99)) ## [[1]] ## integer(0) ## ## [[2]] ## [1] 5 ## ## [[3]] ## [1] 2 3 ## ## [[4]] ## [1] 7 ## ## [[5]] ## [1] 3 3 11
The first one thousand prime numbers.
primesprimes
An integer vector containing the first one thousand prime numbers.
generate_primes, generate_n_primes
Computes the primorial for prime numbers and natural numbers.
primorial_n(n) primorial_p(n)primorial_n(n) primorial_p(n)
n |
an integer indicating the numbers to be used in the computation. See Details for more information. |
The primorial_p function computes the primorial with respect the the first
n prime numbers; while the primorial_n function computes the primorial
with respect the the first n natural numbers.
A numeric vector of length 1.
Paul Egeler, MS
Find pairs of consecutive integers where the prime factors sum to the same
value. For example, (5, 6) are Ruth-Aaron pairs because the prime factors
.
ruth_aaron_pairs(min, max, distinct = FALSE)ruth_aaron_pairs(min, max, distinct = FALSE)
min |
an integer representing the minimum number to check. |
max |
an integer representing the maximum number to check. |
distinct |
a logical indicating whether to consider repeating prime factors or only distinct prime number factors. |
A List of integer pairs.
Paul Egeler, MS