エラトステネスの篩をGolang で実装してみた

2024/7/7追記

コメントでmaxに４を引数とすると4も素数となることをご指摘いただき下記のとおり修正しました。
ご指摘ありがとうございました。

- for i := 2; i < sqrtMax; i++ {
+ for i := 2; i <= sqrtMax; i++ {

サマリー

素数をどうやって算出すればいいか悩んだことはありませんか？
私はありません。

今回は素数を簡単に導出できるアルゴリズムを紹介します。
このアルゴリズムは紙とペンしかない状態でも実行できるので、テストで素数を出さないといけない時が来たときに役立つことでしょう。

今回紹介するアルゴリズムは考案者の名前からエラトステネスの篩(ふるい)(Sieve of Eratosthenes)と呼ばれているアルゴリズムです。
古代ギリシアの科学者であるエラトステネスが考案しました。

今回作成したコード以下で公開しています。
https://github.com/y-miyakaw/sieve_of_Eratosthenes

素数とは

素数(英: prime または prime number)というのは、2以上の自然数かつ正の約数が1と自身のみのもののことです。
例えば5の約数は1と5のみなので素数です。

素数にどんな数字があるかを考えたときに、2, 3, 5, 7, 11, 13あたりまではすんなりと出てくるのですが、100以上とかになるとこれって素数なのか？と時間がかかるようになります。

そんなときに役立つアルゴリズムがエラトステネスの篩です。

エラトステネスの篩の概要

こちらのアルゴリズムを簡単に説明すると、

1. 2から求めたい値までの数値テーブル(今回はslice []bool)を作成し、２以上の値をtrueにする
2. このスライスを先頭から走査する
3. まず2は素数なのでtrueとする
4. 2の倍数は素数ではないので、2の倍数をfalseにする（2を約数に持つため）
5. 続いて3の倍数は素数ではないので、3の倍数をfalseにする
6. この時、6は2の倍数でfalseとなっているので考慮外として良いため、3^2=9以上の3の倍数をfalseとする
7. 続いて5の倍数は素数ではないので、5の倍数をfalseにする
8. この時、10, 15, 20は2の倍数と3の倍数でfalseとなっているので考慮外として良いため、５^2=25以上の5の倍数をfalseとする

上記の走査を継続すると素数のキーのみがtrueで残るので、trueのキーのスライスを作成することで求めたいあたいまでの素数の一覧を作成することができる。

公開したリポジトリと同じものになるが、コードは以下のとおり

package main

import (
	"fmt"
	"math"
)

func main() {
	primes := Sieve(1000)
	fmt.Println(primes)
}

func Sieve(max int) []int {
	if max < 2 {
		return []int{}
	}

	// 走査するスライスを作成
	// Create a slice to track prime candidates
	isPrime := make([]bool, max+1)
	for i := 2; i <= max; i++ {
		isPrime[i] = true
	}

	// maxの平方根を算出
	// Calculate the square root of max
	sqrtMax := int(math.Sqrt(float64(max)))

	// エラトステネスの篩の走査を実行
	// Perform the Sieve of Eratosthenes
	for i := 2; i <= sqrtMax; i++ {
		if isPrime[i] {
			for j := i * i; j <= max; j += i {
				isPrime[j] = false
			}
		}
	}

	// エラトステネスの篩の走査によってtrueとなった数字を素数のスライスに格納
	// Store numbers that remain true after sieving in the primes slice
	primes := make([]int, 0, max/10)
	for i := 2; i <= max; i++ {
		if isPrime[i] {
			primes = append(primes, i)
		}
	}
	return primes
}

まとめ

素数を簡単に導き出すことができるアルゴリズムをgolangで実装してみました。

求めたい値の平方根の値まで走査することで素数がわかる(10000までの素数も100まで走査すればわかる！)ので、紙とペンしかない時でも、比較的簡単に素数を導出できるアルゴリズムになります。

参考