Pairs with common factors: Difference between revisions

</pre>

=={{header|Nim}}==

{{trans|Wren}}

<syntaxhighlight lang="Nim">import std/[sequtils, strutils]

func isPrime(n: Natural): bool =

if n < 2: return false

if (n and 1) == 0: return n == 2

if n mod 3 == 0: return n == 3

var k = 5

while k * k <= n:

if n mod k == 0 or n mod (k + 2) == 0: return false

inc k, 6

result = true

func totient(n: Natural): int =

var n = n

result = n

var i = 2

while i * i <= n:

if n mod i == 0:

while n mod i == 0:

n = n div i

dec result, result div i

if i == 2: i = 1

inc i, 2

if n > 1:

dec result, result div n

const Max = 1_000_000

var a: array[Max, int]

var sumPhi = 0

for n in 1..Max:

inc sumPhi, n.totient

if n.isPrime:

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

else:

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

echo "Number of pairs with common factors - First one hundred terms:"

for n in countup(0, 99, 10):

echo a[n..n+9].mapIt(align($it, 4)).join(" ")

echo()

var limit = 1

while limit <= Max:

echo "The $1th term: $2".format(insertSep($limit), insertSep($a[limit-1]))

limit *= 10

</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 1006 1040 1079 1095 1148 1148 1195

1221 1262 1262 1321 1341 1384 1414 1461 1461 1526

1544 1591 1623 1670 1692 1755 1755 1810 1848 1907

The 1th 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