Amicable pairs: Difference between revisions

=={{header|Forth}}==

{{works with|gforth|0.7.3}}

===Direct approach===

Calculate many times the divisors.

<lang forth>: proper-divisors ( n -- 1..n )

dup 2 / 1+ 1 ?do

dup i mod 0= if i swap then

loop drop ;

: divisors-sum ( 1..n -- n )

dup 1 = if exit then

begin over + swap

1 = until ;

: pair ( n -- n )

dup 1 = if exit then

proper-divisors divisors-sum ;

: ?paired ( n -- t | f )

dup pair 2dup pair

= >r < r> and ;

: amicable-list

1+ 1 do

i ?paired if cr i . i pair . then

loop ;

20000 amicable-list</lang>

{{out}}

<pre>220 284

1184 1210

2620 2924

5020 5564

6232 6368

10744 10856

12285 14595

17296 18416 ok</pre>

===Storage approach===

Use memory to store sum of divisors, a little quicker.

<lang forth>variable amicable-table

: proper-divisors ( n -- 1..n )

dup 1 = if exit then ( not really but useful )

dup 2 / 1+ 1 ?do

dup i mod 0= if i swap then

loop drop ;

: divisors-sum ( 1..n -- n )

dup 1 = if exit then

begin over + swap

1 = until ;

: build-amicable-table

here amicable-table !

1+ dup ,

1 do

i proper-divisors divisors-sum ,

loop ;

: paired cells amicable-table @ + @ ;

: .amicables

amicable-table @ @ 1 do

i paired paired i =

i paired i > and

if cr i . i paired . then

loop ;

: amicable-list

build-amicable-table .amicables ;

20000 amicable-list</lang>

{{out}}

<pre>220 284

1184 1210

2620 2924

5020 5564

6232 6368

10744 10856

12285 14595

17296 18416 ok</pre>