Previous Page Next Page Contents

ifactor -- factor an integer into primes

Introduction

ifactor(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.

Call(s)

ifactor(n <, UsePrimeTab>)
ifactor(PrimeLimit)

Parameters

n - an arithmetical expression representing an integer

Options

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

Returns

an object of domain type Factored, or a symbolic ifactor call.

Related Functions

content, factor, Factored, icontent, igcd, ilcm, isprime, ithprime, nextprime, numlib::divisors, numlib::ecm, numlib::mpqs, numlib::pollard, numlib::prevprime, numlib::primedivisors

Details

Option: UsePrimeTab

Option: PrimeLimit

Example 1

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.

Example 2

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]

Example 3

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"

Background

Changes




Do you have questions or comments?


Copyright © SciFace Software GmbH & Co. KG 2000