## Primes and Factorizations

MuPAD® notebooks will be removed in a future release. Use MATLAB® live scripts instead.

MATLAB live scripts support most MuPAD functionality, though there are some differences. For more information, see Convert MuPAD Notebooks to MATLAB Live Scripts.

### Operate on Primes

Prime numbers are positive integers larger than 1 that have only two positive integer divisors: 1 and the number itself. In MuPAD®, you can check whether the number is prime by using the `isprime` function. For example, 809 is a prime number while 888 and 1 are not primes:

`isprime(809), isprime(888), isprime(1)`

In rare cases, the `isprime` function can return a false positive result. The function performs the Miller-Rabin primality test and uses 10 independent random bases. For a more accurate (and also slower) method, see Proving Primality.

The sequence of prime numbers is infinite. It starts with 2, 3, 5, 7, 11, 13, 17, and goes on. The `ithprime` function lets you quickly find and display any entry of this sequence. For example, to find the 100th prime number, enter `ithprime(100)`:

`ithprime(100)`

To find the prime number that appears in the sequence before a particular value, use the `prevprime` function. To find the prime number that appears after a particular value, use the `nextprime` function. For example, find the prime numbers that precede and follow the number 1000:

`prevprime(1000), nextprime(1000)`

### Note

`prevprime` and `nextprime` use the probabilistic primality test (the Miller-Rabin test). In rare cases, these functions can return nonprime numbers.

MuPAD stores a precalculated table of the prime numbers up to a certain value. The `ifactor` function with the `PrimeLimit` option returns that value:

`ifactor(PrimeLimit)`

The `ithprime` function with the `PrimeLimit` option returns the number of primes in that table:

`ithprime(PrimeLimit)`

The `ithprime` function extracts the prime number from this table. To compute larger prime numbers (which MuPAD does not store in the table), `ithprime` chooses some number as a starting point, and then recursively calls the `nextprime` function. Although the internal algorithm tries to reduce the number of computation steps, computing huge prime numbers can be very slow:

`ithprime(100000000)`

Suppose, you want to display a sequence of prime numbers. For the numbers that MuPAD stores in the table, call the `ithprime` function to find each number in the sequence:

`ithprime(i) \$ i = 1000..1010`

If the numbers exceed the value returned by `ifactor`(`PrimeLimit`), MuPAD does not store them. In this case, calling `ithprime` for each number can be very slow. More efficiently, use `ithprime` to find the first number in the sequence, and then use `nextprime` to find all following numbers:

`(n := ithprime(3*10^7)), (n := nextprime(n + 1)) \$i = 1..10`

To find how many prime numbers do not exceed a particular value, use the `numlib::pi` function:

```numlib::pi(2), numlib::pi(3), numlib::pi(20), numlib::pi(1000), numlib::pi(15.789)```

### Factorizations

You can represent any integer number as a product of primes. This process is called factoring an integer. To factor an integer, use the `ifactor` function. For example, factor the number 362880:

`ifactor(362880)`

### Prove Primality

The function `numlib::proveprime` implements the Atkin-Goldwasser-Kilian-Morain algorithm for proving primality. For information about primality proving and this particular algorithm, see the following papers:

• Atkin, A. O., and F. Morain. “Elliptic curves and primality proving.” Mathematics of Computation. Vol. 61, Number 203, 1993.

• Goldwasser, S., and J. Kilian. “Almost all primes can be quickly certified”. Proceedings of the 18th annual ACM symposium on theory of computing. Berkeley, CA, US, 1986, pp. 316-329.

For relatively small prime numbers, `numlib::proveprime` returns the value `TRUE`. For composite numbers, the function returns `FALSE`:

`numlib::proveprime(541), numlib::proveprime(243)`

For larger prime numbers, `numlib::proveprime` returns a certificate of primality:

`certificate := numlib::proveprime(1299709)`

Generated primality certificates provide all data that you need for proving primality of a number by the Atkin-Goldwasser-Kilian-Morain algorithm. You can substitute the numbers into the algorithm and verify the primality of a number. The `numlib::checkPrimalityCertificate` function can verify the certificate for you:

`numlib::checkPrimalityCertificate(certificate)`

#### Mathematical Modeling with Symbolic Math Toolbox

Get examples and videos