10.20 FactorsInt

FactorsInt( n )

FactorsInt returns a list of the prime factors of the integer n. If the ith power of a prime divides n this prime appears i times. The list is sorted, that is the smallest prime factors come first. The first element has the same sign as n, the others are positive. For any integer n it holds that Product( FactorsInt( n ) ) = n.

Note that FactorsInt uses a probable-primality test (see IsPrimeInt). Thus FactorsInt might return a list which contains composite integers.

The time taken by FactorsInt is approximately proportional to the square root of the second largest prime factor of n, which is the last one that FactorsInt has to find, since the largest factor is simply what remains when all others have been removed. Thus the time is roughly bounded by the fourth root of n. FactorsInt is guaranteed to find all factors less than 10^6 and will find most factors less than 10^{10}. If n contains multiple factors larger than that FactorsInt may not be able to factor n and will then signal an error.

    gap> FactorsInt( -Factorial(6) );
    [ -2, 2, 2, 2, 3, 3, 5 ]
    gap> Set( FactorsInt( Factorial(13)/11 ) );
    [ 2, 3, 5, 7, 13 ]
    gap> FactorsInt( 2^63 - 1 );
    [ 7, 7, 73, 127, 337, 92737, 649657 ]
    gap> FactorsInt( 10^42 + 1 );
    [ 29, 101, 281, 9901, 226549, 121499449, 4458192223320340849 ] 

Previous Up Top Next
Index