
/* factor.q: clib remove_factor example -- find all prime factors of a number,
   along with their multiplicities */

factor 0		= [];
factor N:Int		= factor (-N) if N<0;
			= [(2,K)|factor_from 3 M]
			      where (K,M) = remove_factor N 2
			      if N and 1 = 0; // even number
			= factor_from 3 N
			      otherwise;

factor_from P N		= [] if P > N;
			= [(P,K)|factor_from (P+2) M]
			      where (K,M) = remove_factor N P
			      if N mod P = 0; // P divides N (must be prime)
			= factor_from (P+2) N
			      otherwise; // not a factor, try the next one
