[Go] 素数の個数を求める

はじめに

Goで2以上N以下(Nは任意の自然数)の素数の個数を求める問題を解いていて、いつも素数系の問題ってどうやって解くんだったっけ？となるので備忘録としてまとめておこうと思います。
今回は、標準入力から自然数Nを読み込み、2以上N以下の素数の個数を求めて標準出力に出力します。

対象読者

• 素数判定のアルゴリズムを知りたい人
• Goで素数の個数を数える方法を知りたい人

2以上N以下(Nは任意の自然数)の素数の個数を求める

下記のプログラムではNを標準入力から読み込み、2以上N以下の素数の個数を求めて標準出力に出力します。素数とは、自然数Xの約数が1とXのみであるようなXのことを指します。

プログラム

main.go

package main

import (
	"fmt"
)

func main() {
    // 整数nを標準入力から入力
    var n int
    fmt.Scanf("%d", &n)
    
    // nが2未満なら素数の個数は0個
    if n < 2 {
        fmt.Println(0)
        return
    }
    
    // エラトステネスのふるい
    isPrime := make([]bool, n+1)
    for i := 2; i <= n; i++ {
        isPrime[i] = true
    }
    
    for i := 2; i*i <= n; i++ {
        if isPrime[i] {
            for j := i*i; j <= n; j += i {
                isPrime[j] = false
            }
        }
    }
    
    // 素数の個数を数える
    count := 0
    for i := 2; i <= n; i++ {
        if isPrime[i] {
            count++
        }
    }
    
    // 結果を出力
    fmt.Println(count)
    
}

入力例1

3

出力例1

2

入力例2

10

出力例2

4

エラトステネスのふるい

上記のプログラムでは素数を求めるアルゴリズムとしてエラトステネスのふるいを利用しています。

エラトステネスのふるいとは、指定された自然数以下のすべての素数を効率的に求めるためのアルゴリズムです。このアルゴリズムは、2以上の整数を順に調べていき、その素数の倍数を消去していくことで、最終的に素数のみを抽出します。

まず、make関数を使用してインデックス番号が0からnまでのbool型のisPrimeスライスを作成します。この時、値の全てはfalseで初期化されます。isPrimeスライスの各値はインデックス番号の数字が素数か否かという情報を保持します。

その後のfor文で2以上n以下の値を全てtrueにしています。つまり、初めは2以上n以下のすべての整数が素数だと仮定して、後に素数でないものを省いていきます。

 // エラトステネスのふるい
    isPrime := make([]bool, n+1)
    for i := 2; i <= n; i++ {
        isPrime[i] = true
    }

次に以下の部分で素数でないものを省いていきます。具体的にはisPrimeスライスのインデックス番号が調べる整数を表しているため、素数でない整数のインデックス番号の値をfalseにしていきます。
外側のforループで調べる倍数分ループを回し、内側のforループで調べた倍数の値をfalseにしています。もう少し具体的に言うと、2~30までの素数の個数を調べたいとしたら、5*5 <= 30なので、2,3,4,5の倍数で4回ループを回し、2の倍数の時は2,4,6・・・、3の倍数の時は3,6,9・・・、4の倍数の時はすでに2の倍数で消されている、5の倍数の時は5,10,15・・・と値をfalseにして素数候補から省いていきます。

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

これでisPrimeスライスはインデックス番号の整数が素数か否かである情報を保持するようになりました。

素数の判定ができたらisPrimeスライスの中で素数になっている値(isPrimeの値がtrue)を数えて結果を出力すればOKです。

 // 素数の個数を数える
 count := 0
 for i := 2; i <= n; i++ {
     if isPrime[i] {
         count++
     }
 }

 // 結果を出力
 fmt.Println(count)

まとめ

今回は、Goで2以上N以下(Nは任意の自然数)の素数の個数を求める方法について説明しました。具体的には、標準入力から自然数Nを読み込み、2以上N以下の素数の個数を求めて標準出力に出力します。
素数を数える(判定する)アルゴリズムとして、エラトステネスのふるいを使用しました。