Pairs with common factors: Difference between revisions

=={{header|Go}}==

{{trans|Wren}}

{{libheader|Go-rcu}}

<syntaxhighlight lang="go">package main

import (

"fmt"

"rcu"

)

func totient(n uint64) uint64 {

tot := n

i := uint64(2)

for i*i <= n {

if n%i == 0 {

for n%i == 0 {

n /= i

}

tot -= tot / i

}

if i == 2 {

i = 1

}

i += 2

}

if n > 1 {

tot -= tot / n

}

return tot

}

func ord(c int) string {

m := c % 100

if m >= 4 && m <= 20 {

return "th"

}

m %= 10

switch m {

case 1:

return "st"

case 2:

return "md"

case 3:

return "rd"

default:

return "th"

}

}

func main() {

const max = 1_000_000

a := make([]uint64, max)

sumPhi := uint64(0)

for n := uint64(1); n <= uint64(max); n++ {

sumPhi += totient(n)

if rcu.IsPrime(n) {

a[n-1] = a[n-2]

} else {

a[n-1] = n*(n-1)/2 + 1 - sumPhi

}

}

fmt.Println("Number of pairs with common factors - first one hundred terms:")

rcu.PrintTable(a[:100], 10, 6, true)

fmt.Println()

for limit := 1; limit <= max; limit *= 10 {

fmt.Printf("The %s%s term: %s\n", rcu.Commatize(limit), ord(limit), rcu.Commatize(a[limit-1]))

}

}</syntaxhighlight>

{{out}}

<pre>

Number of pairs with common factors - first one hundred terms:

0 0 0 1 1 4 4 7 9 14

14 21 21 28 34 41 41 52 52 63

71 82 82 97 101 114 122 137 137 158

158 173 185 202 212 235 235 254 268 291

291 320 320 343 363 386 386 417 423 452

470 497 497 532 546 577 597 626 626 669

669 700 726 757 773 818 818 853 877 922

922 969 969 1,006 1,040 1,079 1,095 1,148 1,148 1,195

1,221 1,262 1,262 1,321 1,341 1,384 1,414 1,461 1,461 1,526

1,544 1,591 1,623 1,670 1,692 1,755 1,755 1,810 1,848 1,907

The 1st term: 0

The 10th term: 14

The 100th term: 1,907

The 1,000th term: 195,309

The 10,000th term: 19,597,515

The 100,000th term: 1,960,299,247

The 1,000,000th term: 196,035,947,609

</pre>