GCD Sum

You are given a positive integer $N. Write a script to sum GCD of all possible unique pairs between 1 and $N.

找出來最大公因數 (greatest common divisor) 的和。這裡使用輾轉相除法寫一個取得 gcd 值的函式。

#!/usr/bin/tclsh
#
# You are given a positive integer $N.
# Write a script to sum GCD of all possible unique pairs 
# between 1 and $N.
#

proc gcd {a b} {
    while {$b > 0} {
        set r [::tcl::mathop::% $a $b]
        set a $b
        set b $r
    }

    return $a
}

puts -nonewline "Input: "
flush stdout
gets stdin number
if {$number <= 1} {
    puts "Number requires > 1."
    exit
}

set sum 0
for {set i 1} {$i <= $number} {incr i} {
    for {set j [::tcl::mathop::+ $i 1]} {$j <= $number} {incr j} {
        set value [gcd $i $j]
        set sum [expr $sum + $value]
    }
} 
puts "Output: $sum"

也可以使用 tcllib math::numtheory 套件中的 gcd 函式取得最大公因數的值再加總起來。

#!/usr/bin/tclsh
#
# You are given a positive integer $N.
# Write a script to sum GCD of all possible unique pairs 
# between 1 and $N.
#

package require math::numtheory

puts -nonewline "Input: "
flush stdout
gets stdin number
if {$number <= 1} {
    puts "Number requires > 1."
    exit
}

set sum 0
for {set i 1} {$i <= $number} {incr i} {
    for {set j [::tcl::mathop::+ $i 1]} {$j <= $number} {incr j} {
        set value [math::numtheory::gcd $i $j]
        set sum [expr $sum + $value]
    }
} 
puts "Output: $sum"