# 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 ] ```

GAP 3.4.4
April 1997