% Cosc 2P93: assignment 2
% Winter 2013
% B. Ross

% factor(N, L): Finds prime factors L for integer N.
% Uses factor_case(F, N, Facts) to find a prime factor between 2 and 
% round(sqrt(N)) for N.  If none, then N is prime. Else, adds this factor 
% to solution, and factors remainder.  
% Note that this is not efficient. The "Sieve of Eratosthenes" algorithm
% is a better approach, in which only prime numbers are tested.

factor(N, Flist) :-
	get_a_factor(N, Ans),	
	factor_case(Ans, N, Flist).

factor_case(1, N, [N]).
factor_case(F, N, [F|R]) :-
	F > 1,
	NewN is integer(N/F),
	factor(NewN, R).

% get_a_factor(N, A) finds next prime factor A between 2 and 
% round(sqrt(N)). 

get_a_factor(N, Ans) :-
	Max is round(sqrt(N)),
	check_prime_div(2, Max, N, Ans).
get_a_factor(_, 1).

% check_prime_div(2, Max, N, Ans): 
% Returns first factor Ans between 2 and Max that divides into N
% evenly. Else fails if none exists.

check_prime_div(K, Max, N, K) :-
	K =< Max,
	0 is mod(N, K).
check_prime_div(K, Max, N, Ans) :-
	K =< Max,
	\+ (0 is mod(N, K)),
	K2 is K + 1,
	check_prime_div(K2, Max, N, Ans).