Amicable pairs: Difference between revisions

=={{header|Picat}}==

Different approaches to solve this task:

* foreach loop (two variants)

* list comprehension

* while loop.

Also, the calculation of the sum of divisors is tabled (the table is cleared between each run).

<lang Picat>go =>

N = 20000,

println(amicable1),

time(amicable1(N)),

% initialize_table is needed to clear the table cache

% of sum_divisors/1 between each run.

initialize_table,

println(amicable2),

time(amicable2(N)),

initialize_table,

println(amicable3),

time(amicable3(N)),

initialize_table,

println(amicable4),

time(amicable4(N)),

nl.

% Foreach loop and a map (hash table)

amicable1(N) =>

Pairs = new_map(),

foreach(A in 1..N)

B = sum_divisors(A),

C = sum_divisors(B),

if A != B, A == C then

Pairs.put([A,B].sort(),1)

end

end,

println(Pairs.keys().sort()).

% List comprehension

amicable2(N) =>

println([[A,B].sort() : A in 1..N,

B = sum_divisors(A),

C = sum_divisors(B),

A != B, A == C].remove_dups()).

% While loop

amicable3(N) =>

A = 1,

while(A <= N)

B = sum_divisors(A),

if A < B, A == sum_divisors(B) then

print([A,B]), print(" ")

end,

A := A + 1

end,

nl.

% Foreach loop, everything in the condition

amicable4(N) =>

foreach(A in 1..N, B = sum_divisors(A), A < B, A == sum_divisors(B))

print([A,B]), print(" ")

end,

nl.

%

% Sum of divisors of N

%

table

sum_divisors(N) = Sum =>

sum_divisors(2,N,1,Sum).

% Base case: exceeding the limit

sum_divisors(I,N,Sum0,Sum), I > floor(sqrt(N)) =>

Sum = Sum0.

% I is a divisor of N

sum_divisors(I,N,Sum0,Sum), N mod I == 0 =>

Sum1 = Sum0 + I,

(I != N div I ->

Sum2 = Sum1 + N div I

;

Sum2 = Sum1

),

sum_divisors(I+1,N,Sum2,Sum).

% I is not a divisor of N.

sum_divisors(I,N,Sum0,Sum) =>

sum_divisors(I+1,N,Sum0,Sum).

</lang>

Output:

<pre>

amicable1

[[220,284],[1184,1210],[2620,2924],[5020,5564],[6232,6368],[10744,10856],[12285,14595],[17296,18416]]

CPU time 0.114 seconds.

amicable2

[[220,284],[1184,1210],[2620,2924],[5020,5564],[6232,6368],[10744,10856],[12285,14595],[17296,18416]]

CPU time 0.106 seconds.

amicable3

[220,284] [1184,1210] [2620,2924] [5020,5564] [6232,6368] [10744,10856] [12285,14595] [17296,18416]

CPU time 0.111 seconds.

amicable4

[220,284] [1184,1210] [2620,2924] [5020,5564] [6232,6368] [10744,10856] [12285,14595] [17296,18416]

CPU time 0.107 seconds.

</pre>