Posted at

Golangで雑に素数を計算したよ

More than 1 year has passed since last update.

フィクションに出てくる数学者キャラは大抵素数にこだわりがあってなんかカッコイイ。

ところで「そこまでに出た素数で割り切れる数は素数じゃないって前提に立てば簡単に素数を算出できるプログラム書けるんじゃね?」って急に思ったので書いてみた。

ついでにGolangもやってみたかったからGolangで書いた。


結果から先に言うと

結果動いたけどやっぱりある程度以上からものすごく重くなった。

あと、Golangに素数をまんま出せるライブラリあったらやってることアホだなって思って一応調べてみたところ(結果なさそうではあった)、なんか素数業界が色々ガチっぽくて怖ぇ!ってなったので素数のタグはつけないことにした。


作ったもの


コード

package main

import (
"fmt"
"math"
)

func main() {
prime_numbers := []float64{2}
var test_max_number float64 = float64(math.Pow(10, 5))
var n,m,dm,prime_number float64

for n = 1; n < test_max_number; n++ {
m = (n * 2) + 1

is_not_prime := false
for _, prime_number = range prime_numbers{
dm = m / prime_number
if dm == math.Ceil(dm) {
is_not_prime = true
break
}
}

if is_not_prime == false{
prime_numbers = append(prime_numbers, m)
}

}

fmt.Println(prime_numbers)

}


実行環境


  • macOS High Sierra Version 10.13.1

  • go version go1.9.2 darwin/amd64


経過と結果


  • まずは20(10の1乗 * 2)までの状況で開発し、計算結果を目視で確認していける!って思った。

  • 次に2,000(10の3乗 * 2)くらいまで計算させてwikipediaの素数の記事と比べてみたらだいたいあってたのでこれは多分ほんといける!って思った。

  • 次に20万(10の5乗 * 2)にしたところで1秒くらいで答えが返ってきたけど、乗数を1つあげて200万にしたところ10秒待っても返ってこなくなり、そこで諦めた。


ガチっぽい素数業界について

Golangで「エラトステネスの篩」で「2.1秒で百万個」の素数を計算できる「無限シーケンス」を作ってみた

とか。

Golangで「エラトステネスの篩」で「1.3秒で百万個」の素数を計算できる「無限シーケンス」を作ってみた

とか。

Python/Ruby/PHP/Golang(Go)で素数を扱う

とか。

「エラストテネスの篩」って名前がもうカッコイイ。