Code Review: sort by number of prime factors

[razetime]

This program is an attempt at Perl Weekly Challenge 241.

:- use_module(library(clpz)).
:- use_module(library(reif)).
:- use_module(library(pairs)).

r_div(A,B,true):-A mod B#=0.
r_div(A,B,false):-A mod B#>0.

np_(C,_,1,C).
np_(C,Cp,N,P):-
	if_(
  	r_div(N,Cp),
  	(Q#=N/Cp,D#=C+1,np_(D,Cp,Q,P)),
  	(Np#=Cp+1,np_(C,Np,N,P))
	).
np(N,P):-np_(0,2,N,P).
ch2(A,S):-maplist(np,A,B),pairs_keys_values(P,B,A),keysort(P,Q),pairs_values(Q,S).

The recursion I have implemented in np_ implicates an infinite number of solutions that point at the same result, resulting in ch2 also doing the same.

I have tried using if_/3 for checking the N=1 case instead, which works, but i was wondering if i could make this work with the pattern match as well.

[triska]

Very interesting, thank you a lot for sharing this!

To remove the infinitely many redundant solutions, I think it suffices to add N #> 1 to the second clause np_/4.

The predicate zcompare/3 from library(clpz) lets us reify the outcome of arithmetic comparisons, so that argument indexing improves determinism:

np_(C,Cp,N,P):-
        zcompare(Comp, N, 1),
        c_np_(Comp, C, Cp, N, P).

c_np_(=, C, _, _, C).
c_np_(>, C, Cp, N, P) :-
	if_(r_div(N,Cp),
            (Q#=N/Cp,D#=C+1,np_(D,Cp,Q,P)),
            (Np#=Cp+1,np_(C,Np,N,P))).

With if_/3 or zcompare/3, we can also easily make r_div/3 deterministic for the given usage mode, while retaining its full generality:

r_div(A, B, T) :-
        A mod B #= R,
        if_(R = 0, T = true, T = false).

Yielding:

?- np(27, N).
   N = 3.
?- ch2([11,8,27,4], Ls).
   Ls = [11,4,8,27].

Note that library(lists) must also be loaded, for maplist/3 which is used in the code!