友好数

main.go

package main

import (
	"fmt"
	"runtime/debug"
)

var (
	primeNumbers []int
	pairNumbers []int
	maxValue = 100_000_000
)

func init() {
	debug.SetMaxStack(3_000_000_000)
	primeNumbers = PrimeNumbers(maxValue)
	// fmt.Println(len(primeNumbers))
	pairNumbers = make([]int, 2*maxValue+1, 2*maxValue+1)
}

func PrimeNumbers(n int) []int {
	var numbers []int
	length := n + 1
	v := make([]int, length, length)
	for i:=2; i<=n; i++ {
		if v[i] == 0 {
			numbers = append(numbers, i)
			for j:=2*i; j<length;j+=i{
				v[j] = 1
			}
		}
	}
	return numbers
}

func Calculate(pos int, x int, pairSum int) {
	itemSum := 0
	currX := x
	for item:=1; ; item *= primeNumbers[pos] {
		itemSum += item
		if item != 1 {
			currX *= primeNumbers[pos]
		}

		if currX <= 2*maxValue {
			currPairSum := pairSum * itemSum
			if item != 1 {
				pairNumbers[currX] = currPairSum - currX
			}
			if pos + 1 < len(primeNumbers) && (item != 1 || currX * primeNumbers[pos] < 2*maxValue) {
				Calculate(pos+1, currX, currPairSum)
			}
		} else {
			break
		}
	}
}

func main() {
	// https://www.v2ex.com/t/655363
	Calculate(0, 1, 1)
	var result []int
	for x:=2; x<=maxValue; x+=1 {
		y := pairNumbers[x]
		if x!=y && y <= 2*maxValue && pairNumbers[y] == x {
			result = append(result, x)
		}
	}
	fmt.Println(len(result))
}