【Project Euler】#012

12問目です！

問題

三角数の列は自然数を加算して生成されます。したがって、第 7 番目の三角数は $1 + 2 + 3 + 4 + 5 + 6 + 7 = 28$ となります。最初の10個の項は以下の通りです:
$1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...$

最初の7つの三角数の約数を列挙してみましょう:

$1: 1$
$3: 1,3$
$6: 1,2,3,6$
$10: 1,2,5,10$
$15: 1,3,5,15$
$21: 1,3,7,21$
$28: 1,2,4,7,14,28$

ここで、$28$ が初めて5個を超える約数を持つ三角数であることが分かります。
では、500個を超える約数を持つ最初の三角数の値はいくつでしょうか？

わたしの回答

func solve() {
	x, y := 1, 0
	for {
		if 500 <= count(y) {
			break
		}
		y += x
		x++
	}
	fmt.Println(y)
}

// 約数をカウントする関数
func count(num int) int {
	if num == 1 {
		return 1
	}
	x := 2
	count := 1
	for x*x <= num {
		if num%x == 0 {
			if x*x == num {
				count++
			} else {
				count = count + 2
			}
		}
		x++
	}
	return count
}

1. 三角数をループで求め続ける。
2. 約数数を計算する。
3. 約数数が500以上の三角数が見つかったらループ終了。
   といった感じです。

約数計算は...。

1. 2で割り切れたら、その対となる数字の分もカウント。
2. 3で割り切れたら、その対となる数字の分もカウント。
3. ...。
4. 平方根で割り切れたら、対は同じ数なのでカウントは1。

約数計算だけちょこっと工夫しました。

GPT-4oの回答

func countDivisors(n int) int {
	if n == 1 {
		return 1
	}

	count := 1
	num := n

	for i := 2; i <= int(math.Sqrt(float64(num))); i++ {
		exp := 0
		for num%i == 0 {
			exp++
			num /= i
		}
		if exp > 0 {
			count *= (exp + 1)
		}
	}
	if num > 1 {
		count *= 2
	}
	return count
}

// 最初に約数がlimitを超える三角数を探す
func findTriangleNumberWithDivisors(limit int) int {
	n := 1
	for {
		triangle := n * (n + 1) / 2

		// 三角数の約数数を効率よく求めるために、nと(n+1)の約数数を別に求める
		var divCount int
		if n%2 == 0 {
			divCount = countDivisors(n/2) * countDivisors(n+1)
		} else {
			divCount = countDivisors(n) * countDivisors((n+1)/2)
		}

		if divCount > limit {
			return triangle
		}
		n++
	}
}

func solve() {
	result := findTriangleNumberWithDivisors(500)
	fmt.Println("The first triangle number with over 500 divisors is:", result)
}

あー、そういうことか。
素因数分解する感じなんですね。

for i := 2; i <= int(math.Sqrt(float64(num))); i++ {
    exp := 0
    for num%i == 0 {
        exp++
        num /= i
    }
    if exp > 0 {
        count *= (exp + 1)
    }
}

Gemini2.5 Proの回答

// 約数の数を計算する関数
func countDivisors(n int) int {
	count := 0
	sqrtN := int(math.Sqrt(float64(n)))
	for i := 1; i <= sqrtN; i++ {
		if n%i == 0 {
			count += 2
		}
	}
	if sqrtN*sqrtN == n {
		count--
	}
	return count
}

func solve() {
	num := 1
	triangleNumber := 0
	for {
		triangleNumber += num
		if countDivisors(triangleNumber) > 500 {
			fmt.Println(triangleNumber)
			break
		}
		num++
	}
}

平方根の求め方以外は、ほとんどわたしのロジックと流れが同じようですね。

ベンチマーク

計測	実行回数 (b.N)	平均実行時間 (ns/op)
わたしの回答	25	46,459,480 ns/op
GPT4.1	892	1,446,054 ns/op
Gemini2.5	24	46,290,273 ns/op

Geminiには僅差で勝ちました🦖

感想

GPTには素因数分解を見せつけられましたが、Geminiにはなんと勝てたのでよかったです。