blob: b69528139521494c147820c049dbe118d8671657 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
\ Challenge 089
\
\ TASK #1 � GCD Sum
\ Submitted by: Mohammad S Anwar
\ You are given a positive integer $N.
\
\ Write a script to sum GCD of all possible unique pairs between 1 and $N.
\
\ This solution uses a recursive algorithm to compute the GCD.
: gcd { a b -- gcd }
a 0= IF
b \ return b
ELSE
b a MOD a RECURSE \ recurse to return gcd(b MOD a, a)
THEN
;
: sum_gcd { n -- sum }
0 \ push initial sum
n 1 ?DO \ I: 1 .. n-1
n 1+ I 1+ ?DO \ J: I+1 .. n
I J gcd + \ accumulate gcd
LOOP
LOOP
;
NEXT-ARG S>NUMBER? 0= THROW DROP
sum_gcd . CR BYE
|
