blechmusikの日記

いろいろなことを書いています。

AutoHotkey でハッシュ法を使用するために素数を生成する関数を作成した

以下は、引数を2倍した数値未満で最大の素数を返す関数だ。

;;; Archives academic 素数判定プログラム
;;; http://www.usamimi.info/~geko/arch_acade/elf009_prime/index.html

;;; 上記のスクリプトから 2 の素数を判定に用いる処理を省いた

;;; (引数 * 2) 未満且つ最大の素数を返す関数
Return_MaxPrimeNumber_ForHashing(DataSize)
{
    N := DataSize * 2
    PrimeNumber_List := "3|5|"
    MaxPrimeNumber := 5

    Loop, % N // 6
    {
        x1 := (6 * A_Index) + 1
        x2 := x1 + 4

        if (x1 > N)
            Break

        Loop, Parse, PrimeNumber_List,|
        {
            if (A_LoopField > Sqrt(x1))
            {
                PrimeNumber_List .= x1 . "|"
                MaxPrimeNumber   := x1

                Break
            }

            if ((mod(x1, A_LoopField)) = 0)
                Break
        }

        if (x2 > N)
            Break

        Loop, Parse, PrimeNumber_List,|
        {
            if (A_LoopField > Sqrt(x2))
            {
                PrimeNumber_List .= x2 . "|"
                MaxPrimeNumber   := x2

                Break
            }

            if ((mod(x2, A_LoopField)) = 0)
                Break
        }
    }

    return MaxPrimeNumber
}

処理速度は少々遅いかもしれない。私の環境での具体的結果を示そう。1,000 未満でかつ最大の素数を返すまでの処理時間は 1 ミリ秒未満だ。10,000 未満でかつ最大の素数を返すまでの処理時間は 100 ミリ秒前後である。100,000 未満でかつ最大の素数を返すまでの処理時間は 3.3 秒前後である。
DvorakJ のハッシュ法の処理にこの関数により生成した素数を取り入れる予定だ。


参考:

引数がメルセンヌ数かを判定する AutoHotkey 用スクリプトである。


追記:

この手法をうまく採用するとさらに高速化できるかもしれない。

;;; Print Prime Numbers
;;; http://www.rsok.com/~jrm/printprimes.html

;;; (引数 * 2) 未満且つ最大の素数を返す関数
Return_MaxPrimeNumber_ForHashing(DataSize)
{
    N := DataSize * 2

    if (N < 31)
    {
        MaxPrimeNumber  :=   (N < 3)  ? 2
                        :    (N < 5)  ? 3
                        :    (N < 7)  ? 5
                        :    (N < 11) ? 7
                        :    (N < 13) ? 11
                        :    (N < 17) ? 13
                        :    (N < 19) ? 17
                        :    (N < 23) ? 19
                        :    (N < 29) ? 23
                        :               29
    }
    else
    {
        PrimeNumber_CheckingList := "3|5|7|11|13|17|19|23|29"
        PrimeNumber_MakingList   :=   "1|7|11|13|17|19|23|29"
        MaxPrimeNumber := 29

        Loop, % N // 30
        {
            ;; 30 の倍数
            LoopTimes_30 := 30 * A_Index

            Loop, Parse, PrimeNumber_MakingList, |
            {
                ;; 30 の倍数に PrimeNumber_MakingList の項目を一つずつ加えて値を作り出す
                i := LoopTimes_30 + A_LoopField

                ;; 作成した値が N を超えるときは処理を終了する
                if (i > N)
                {
                    Break
                }
                else
                {
                    Loop, Parse, PrimeNumber_CheckingList, |
                    {
                        if(A_LoopField > sqrt(i))
                        {
                            ;; PrimeNumber_CheckingList に作成した値を追加する
                            PrimeNumber_CheckingList .= "|" . i
                            MaxPrimeNumber := i

                            Break
                        }
                        else
                        if (mod(i, A_LoopField) = 0) ; 剰余が 0 のとき
                        {
                            Break
                        }
                    }
                }
            }
        }
    }

    return MaxPrimeNumber
}

これでは処理の時間をそれほど短縮できないようだ。1,000 未満でかつ最大の素数を返すまでの処理時間は 1 ミリ秒未満だ。10,000 未満でかつ最大の素数を返すまでの処理時間は 90 ミリ秒前後である。100,000 未満でかつ最大の素数を返すまでの処理時間は 3.2 秒前後である。
これらとは異なる方法を使用しようか。