【Project Euler】#010

10問目です！

問題

The sum of the primes below $10$ is $2 + 3 + 5 + 7 = 17$.
Find the sum of all the primes below two million.

2000000未満の素数の和を求める問題ですね。
素数問題多いですね。

わたしの回答

func solve() {
	sum := 0
	for i := 2; i < 2000000; i++ {
		if isPrimeNumber(i) {
			sum += i
		}
	}
	fmt.Println(sum)
}

func isPrimeNumber(num int) bool {
	x := 2
	for x*x <= num {
		if num%x == 0 {
			return false
		}
		x++
	}
	return true
}

2~200000でループを回して、素数だったら変数sumを更新していく、というロジックです。

GPT-4.1の回答

func solve() {
	const limit = 2000000
	isPrime := make([]bool, limit)
	for i := 2; i < limit; i++ {
		isPrime[i] = true
	}

	for i := 2; i*i < limit; i++ {
		if isPrime[i] {
			for j := i * i; j < limit; j += i {
				isPrime[j] = false
			}
		}
	}

	sum := 0
	for i := 2; i < limit; i++ {
		if isPrime[i] {
			sum += i
		}
	}

	fmt.Println("Sum of all primes below 2 million:", sum)
}

ちょっと理解に苦しんだんですが、素数かどうかをふるいにかけていく感じのようです。

1. 最大制限値までの整数をキーにした素数かどうかを判定する連想配列を生成(デフォルトTRUE)
2. 連想配列をループさせる。
3. 素数フラグがTRUEであれば、その倍数の素数フラグを全部FALSEにする。
4. 連想配列を再度ループさせて、素数フラグがTRUEのものを加算していく。

理解できました。でも、2のループと4のループは処理まとめれると思います。

Gemini2.5 Flashの回答

func solve() {
	limit := 2000000
	isPrime := make([]bool, limit+1)

	for i := 0; i <= limit; i++ {
		isPrime[i] = true
	}

	isPrime[0] = false
	isPrime[1] = false

	for p := 2; p*p <= limit; p++ {
		if isPrime[p] == true {
			for i := p * p; i <= limit; i += p {
				isPrime[i] = false
			}
		}
	}

	var sum int64 = 0
	for i := 2; i <= limit; i++ {
		if isPrime[i] == true {
			sum += int64(i)
		}
	}

	fmt.Printf("200万以下の素数の合計は: %d\n", sum)
}

GPT4.1の解き方とほぼ同じですね。

ベンチマーク

計測	実行回数 (b.N)	平均実行時間 (ns/op)
わたしの回答	9	118,894,889 ns/op（約119ミリ秒）
GPT4.1	322	3,493,777 ns/op（約3.49ミリ秒）
Gemini2.5	321	3,505,954 ns/op（約3.51ミリ秒）

感想

GPTとGeminiに置いてけぼりにされました。
いくら平方根での計算だとしても、ふるいにかけたほうが速いのか...。