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

private factor_from;

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

factor_from P N		= [] if P > N;
			= [(P,fact N P)|factor_from (P+2) (rem 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