ifactor
-- factor an integer
into primesifactor(
n)
computes the prime
factorization n = s * p1^^e1 * ... * pr^er of the integer
n, where s is the sign of n,
p1,...,pr are the distinct positive prime divisors of
n, and e1,...,er are positive integers.
ifactor(n <, UsePrimeTab>)
ifactor(PrimeLimit)
n |
- | an arithmetical expression representing an integer |
UsePrimeTab |
- | look only for those prime factors that are stored in the internal prime table of the system |
PrimeLimit |
- | return the bound on the largest prime number in the prime table |
an object of domain type Factored
, or a symbolic
ifactor
call.
content
, factor
, Factored
, icontent
, igcd
, ilcm
, isprime
, ithprime
, nextprime
, numlib::divisors
, numlib::ecm
, numlib::mpqs
, numlib::pollard
, numlib::prevprime
, numlib::primedivisors
ifactor
is an object of domain type
Factored
. Let
f:=ifactor(n)
be such an object. Internally, it is
represented by the list [s, p1, e1,
..., pr, er]
of odd length 2r+1, where r
is the number of distinct prime divisors of n. The
pi are not necessarily sorted by magnitude.
You may extract the sign s, the primes pi, as
well as the exponents ei by means of the index operator
[ ]
, so that f[1] = s, f[2]
= p1, f[3] = e1, ...
.
For example, the command f[2*i] $ i = 1..nops(f) div 2
returns all distinct prime divisors of n. The call
Factored::factors(f)
yields the same result, and
Factored::exponents(f)
returns a list of the exponents
ei for 1 <= i <= r.
The factorization of 0, 1, and -1
yields the single factor 0, 1, and -1,
respectively. In these cases, the internal representation is the list
[0]
, [1]
, and [-1]
,
respectively.
The call coerce(f,DOM_LIST)
returns the
internal representation of a factored object, i.e., the list as
described above.
Note that the result of ifactor
is printed as an
expression, and it is implicitly converted into an expression whenever
it is processed further by other MuPAD functions. For example,
the result of ifactor(
12)
is printed as
2^2*3
, which is an expression
of type "_mult"
.
See example 1 for illustrations, and
the help page of Factored
for more details.
n
, but
only want to know whether it is composite or prime, use isprime
instead, which is much
faster.ifactor
returns an error when the argument is a number
but not an integer. A symbolic
ifactor
call is returned if the argument is not a number.ifactor(
n, UsePrimeTab)
looks only for prime factors
that are stored in this internal prime number table, extracts them from
n
, and returns the undecomposed product of all other prime
factors as a single factor. This is usually much faster than without
the option UsePrimeTab, but it does not
necessarily yield the complete prime factorization of n
.
See example 2.ifactor(
PrimeLimit)
returns an integer, namely the bound on the largest prime number in the
internal prime number table. The table contains all primes below this
bound. The default values are: 1 000 000 on
UNIX systems, and 300 000 on MacOS and Windows
platforms.
On UNIX platforms, the size of this table can be changed via the
MuPAD command line flag
-L
.
To get the prime factorization of 120, enter:
>> f := ifactor(120)
3 2 3 5
You can access the internal representation of this factorization using the index operator:
>> f[1]; // the sign f[2*i] $ i=1..nops(f) div 2; // the factors f[2*i + 1] $ i=1..nops(f) div 2; // the exponents
1 2, 3, 5 3, 1, 1
The internal representation of f
, namely
the list as described above, is returned by the following command:
>> coerce(f, DOM_LIST)
[1, 2, 3, 3, 1, 5, 1]
The result of ifactor
is an object of
domain type Factored
:
>> domtype(f)
Factored
This domain implements some features for handling such objects. Some of them are described below.
You may extract the factors and exponents of the factorization also in the following way:
>> Factored::factors(f), Factored::exponents(f)
[2, 3, 5], [3, 1, 1]
You can ask for the type of the factorization:
>> Factored::getType(f)
"irreducible"
This output means that all pi are prime.
Other possible types are "squarefree"
(see polylib::sqrfree
) or
"unknown"
.
Multiplying factored objects preserves the factored form:
>> f2 := ifactor(12)
2 2 3
>> f*f2
5 2 2 3 5
It is important to note that you can apply nearly any
function operating on arithmetical expressions to an object of domain
type Factored
. The
result is usually not of this domain type:
>> expand(f); domtype(%)
120 DOM_INT
The function type
implicitly converts an object of
domain type Factored
into an expression:
>> type(f)
"_mult"
For a detailed description of these objects, please
refer to the help page of the domain Factored
.
The factorizations of 0
, 1
,
and -1
each have exactly one factor:
>> ifactor(0), ifactor(1), ifactor(-1)
0, 1, -1
>> map(%, coerce, DOM_LIST)
[0], [1], [-1]
The internal representation of the factorization of a
prime number p
is the list [1, p, 1]
:
>> coerce(ifactor(5), DOM_LIST)
[1, 5, 1]
The bound on the prime number table is:
>> ifactor(PrimeLimit)
1000000
We assign a large prime number to p
:
>> p := nextprime(10^12)
1000000000039
Completely factoring the 36
digit number
6*p^3
takes some time; the second output line shows the
time in seconds:
>> t := time(): f := ifactor(6*p^3); (time() - t)/1000.0
3 2 3 1000000000039 12.34
>> Factored::getType(f)
"irreducible"
Extracting only the prime factors in the prime table is much faster, but it does not yield the complete factorization; the factor p^3 remains undecomposed:
>> t := time(): f := ifactor(6*p^3, UsePrimeTab); (time() - t)/1000.0
2 3 1000000000117000000004563000000059319 0.21
>> Factored::getType(f)
"unknown"
ifactor
uses the elliptic curve method.
ifactor
is an interface to the kernel function
stdlib::ifactor
. It calls stdlib::ifactor
with the given arguments and convert its result, which is the list
[s, p1, e1, ..., pr, er]
as described above, into an
object of the domain type Factored
.
You may directly call the kernel function
stdlib::ifactor
inside your routines, in order to avoid
this conversion and to decrease the running time.
ifactor
is an object of domain
type Factored
.