Factors of an integer: Difference between revisions

=={{header|Picat}}==

===List comprehension===

<lang Picat>factors(N) = [[D,N // D] : D in 1..N.sqrt.floor, N mod D == 0].flatten.sort_remove_dups.</lang>

===Recursion===

{{trans|Prolog}}

<lang Picat>factors2(N,Fs) :-

integer(N),

N > 0,

Fs = findall(F,factors2_(N,F)).sort_remove_dups.

factors2_(N,F) :-

L = floor(sqrt(N)),

between(1,L,X),

0 == N mod X,

( F = X ; F = N // X ).</lang>

===Loop using set===

<lang Picat>factors3(N) = Set.keys.sort =>

Set = new_set(),

Set.put(1),

Set.put(N),

foreach(I in 1..floor(sqrt(N)), N mod I == 0)

Set.put(I),

Set.put(N//I)

end.</lang>

===Comparison===

Let's compare with 18! (6402373705728000) which has 14688 factors. The recursive version is slightly faster than the loop + set version.

<lang Picat>go =>

N = 6402373705728000, % factorial(18),

println("factors:"),

time(_Fs1 = factors(N)) ,

println("factors2:"),

time(factors2(N,_Fs2)),

println("factors3:"),

time(Fs3=factors3(N)).len),

</lang>

{{out}}

<pre>factors:

CPU time 3.938 seconds.

factors2:

CPU time 3.108 seconds.

factors3:

CPU time 3.159 seconds.</pre>