Become an expert in R — Interactive courses, Cheat Sheets, certificates and more!
Get Started for Free

isprime

Determine if number is (very probably) prime


Description

Determine whether the number n is prime or not, with three possible answers:

2:

n is prime,

1:

n is probably prime (without beeing certain),

0:

n is composite.

Usage

isprime(n, reps = 40)

Arguments

n

integer number, to be tested.

reps

integer number of primality testing repeats.

Details

This function does some trial divisions, then some Miller-Rabin probabilistic primary tests. reps controls how many such tests are done, 5 to 10 is already a resonable number. More will reduce the chances of a composite being returned as “probably prime”.

Value

0

n is not prime

1

n is probably prime

2

n is prime

Author(s)

Antoine Lucas

References

The GNU MP Library, see https://gmplib.org

See Also

Note that for “small” n, which means something like n < 10'000'000, non-probabilistic methods (such as factorize()) are fast enough. For example, primes in package sfsmisc.

Examples

isprime(210)
isprime(71)

# All primes numbers from 1 to 100
t <- isprime(1:99)
(1:99)[t > 0]

table(isprime(1:10000))# 0 and 2 : surely prime or not prime

primes <- function(n) {
  ## all primes <= n
  stopifnot(length(n) == 1, n <= 1e7) # be reasonable
  p <- c(2L, as.integer(seq(3, n, by=2)))
  p[isprime(p) > 0]
}

## quite quickly, but for these small numbers
## still slower than e.g., sfsmisc::primes()
system.time(p100k <- primes(100000))

## The first couple of Mersenne primes:
p.exp <- primes(1000)
Mers <- as.bigz(2) ^ p.exp - 1
isp.M <- sapply(seq_along(Mers), function(i) isprime(Mers[i], reps=256))
cbind(p.exp, isp.M)[isp.M > 0,]
Mers[isp.M > 0]

gmp

Multiple Precision Arithmetic

v0.6-2
GPL (>= 2)
Authors
Antoine Lucas, Immanuel Scholz, Rainer Boehme <rb-gmp@reflex-studio.de>, Sylvain Jasson <Sylvain.Jasson@inrae.fr>, Martin Maechler <maechler@stat.math.ethz.ch>
Initial release
2021-01-07

We don't support your browser anymore

Please choose more modern alternatives, such as Google Chrome or Mozilla Firefox.