DEAD

# prime_factors

Definition: | sequence s = prime_factors(atom n, bool duplicates=false, integer maxprime=100)
Description: | Returns a list of prime factors of n, which must be an integer (as stored in an atom) between 0 and power(2,iff(machine_bits()=32?53:64)). Note that, when duplicates is false, prime_factors() always returns {} when passed a prime number (or 1). If n is 0 the result is {}, irrespective of any other setting. When duplicates is true, returns a list such that multiplying all the elements of it together produces the value n, ie a true decomposition. In fact, prime_factors(1,true) yields {1} as a special case to fulfil that requirement, despite 1 not actually being a prime number. That special case is also the one and only time the result can ever contain a 1. The maxprime argument limits the number of prime number factors that are checked, for more details see mpz_prime_factors(), which is also capable of handling much larger inputs. The get_maxprime() function can be used to obtain a suitable maxprime index by performing a fast binary_search() for floor(sqrt(p)), which ensures all appropriate primes are checked. However that routine is unlikely to be suitable for mpz_prime_factors() for reasons outlined therein. Alternatively you can pass -1 to maxprime (in this routine) and have it invoke get_maxprime() for you, but of course that potentially means an unnecessary sqrt() and binary_search() every time. Values above the stated limits trigger an exception, since otherwise the dropped bits would make the result quite incorrect and utterly meaningless. Should you by some strange circumstance happen to know that several trailing bits of a very large n are meant to be 0 (something this routine could not possibly test) and therefore there really isn&rsquot any precision loss, I supppose you could divide by power(2,k) and prepend repeat(2,k) to the head of the result, for some k.
Auxillary functions: | bool res = square_free(atom n, integer maxprime=100) returns true if prime_factors(n,true,maxprime) would contain no duplicates, but without constructing any unnecessary internal lists, and quitting early on failure. square_free(0) yields true, because it is. bool res = is_prime(atom n) returns true when prime_factors(n,false,get_maxprime(p)) would yield {}, but using a faster/simplified version of almost the same algorithm. is_prime(0) yields false, because it isn’t. Bear in mind, however, that while this is pretty fast, even on 15 or 16 digit numbers, it is still a trial division approach and no doubt mpz_prime() will be much faster on larger numbers, plus of course not bound by any 53/64 bit precision limts. The checks on the legal range of n and handling of -1 in maxprime as noted above apply equally to these routines.
Example: |
    s = prime_factors(6) -- s is {2,3}
    s = prime_factors(720) -- s is {2,3,5}
    s = prime_factors(12345) -- s is {3,5,823}
    s = prime_factors(27) -- s is {3}
    s = prime_factors(27,duplicates:=true) -- s is {3,3,3}
    atom a = power(2*get_prime(101),2)
    s = prime_factors(a,true)       -- s is {2,2,299209}
    s = prime_factors(a,true,101)   -- s is {2,2,547,547}
In contrast, factors(720) is {2,3,4,5,6,8,9,10,12,15,16,18,20,24,30,36,40,45,48,60,72,80,90,120,144,180,240,360}, and factors(12345) is {3,5,15,823,2469,4115}. The use of a named parameter when setting the duplicates flag is recommended, to make the intent clear and the code easier to read.
Implementation: | See builtins\pfactors.e (an autoinclude) for details of the actual implementation.
See Also: | factors, power, iff, machine_bits, mpz_prime_factors, get_maxprime