素数関係

NScripter&Luaで素数 - 永字八法の続き。
今のLua理解でもう一度発明をしてみる。

ライブラリ

これをはりつけると、一つのテーブルと二つの関数が追加される。

math.prime_list

素数列のテーブル。prime_list[10]とすると、10番目の素数（＝31）が戻ってくる。

math.is_prime(num)

関数。数値を与えると、それが素数かどうかをbooleanで返す。

math.is_not_prime(num)

関数。math.is_prime(num)の逆の結果になる。

do
	-- 素数列の配列。1には2が、2には3が、3には5が……入っている。
	prime_list = setmetatable({2, 3}, {__index=function(prime_list, key)
		if type(key)~="number" then return nil end -- キーは数字でなければ！
		key = math.floor(key) -- 整数でないと！

		local temp = prime_list[key-1] + 2 -- 初期設定は、一つ前＋２
		local is_not_prime = false -- 素数かどうかの判定フラグ
		local copy
		while true do
			for i, prime in ipairs(prime_list) do -- 小さな素数から順番に試していく。
				if prime > 2 then -- 素数2では試さない。
					if prime * prime > temp then break end -- 素数の平方を超えたら終了。
					copy = temp -- 試す数値をコピー
					while copy > 0 do copy = copy - prime end -- ずっと減らしていく。
					is_not_prime = (copy==0) -- copyの値が0なら割り切れたことになり、これは素数ではない。
					if is_not_prime then break end -- 素数でないことがわかったなら、ループ終了。
				end
			end
			if is_not_prime then -- 素数でないならば、試す数値を2増やして再トライ
				temp = temp + 2
			else -- 素数ならば、ループを終了
				break
			end
		end

		rawset(prime_list, key, temp) -- セットする。
		return rawget(prime_list, key) -- セットした物を返す。
	end})
	math.prime_list = prime_list

	-- その数値が素数かどうかを調べる。
	local is_prime_memo = {} -- 調べた結果を格納しておく。
	local func = function(num)
		if num < 2 then return false end
		if type(is_prime_memo[tostring(num)]) ~= "nil" then return is_prime_memo[tostring(num)] end -- メモがあればそれを使う。
		local cursor = #prime_list -- 調べる場所
		local res = false
		local search_list = {}
		while true do
			if search_list[cursor] then break end -- 一度調べたところなら、パスする。
			search_list[cursor] = true
			if prime_list[cursor]==num then -- 素数列内に同値があったならば、それは素数である。
				res = true
				break
			end
			if prime_list[cursor]<num then -- カーソル位置の素数よりも、試す数値が高いならば、
				cursor = cursor + 1 -- カーソルを一つ増やす。
			else -- 逆に低いならば
				cursor = cursor - 1 -- カーソルを一つ減らす。
			end
		end
		is_prime_memo[tostring(num)] = res -- 結果をメモに保存。
		return res -- 結果を返す。
	end
	math.is_prime = func
	math.is_not_prime = function(num)
		if func(num) then return false else return true end
	end
end

おまけ

以下のスクリプトを使うと、NScirpter側に二つの命令が追加される。

-- prime命令。
-- prime %0,%1
-- 素数列の最初を1として、%1番目の素数を%0に格納する。
NSExec("luasub prime")
function NSCOM_prime()
	local ref = NSPopIntRef()
	NSPopComma()
	NSSetIntValue(ref, math.prime_list[NSPopInt()])
end

-- is_prime命令
-- is_prime %0,%1
-- %1が素数かどうか判定して、結果を%0に入れる。素数なら1、そうでなければ0が入る。
NSExec("luasub is_prime")
function NSCOM_is_prime()
	local res = 0
	local ref = NSPopIntRef()
	NSPopComma()
	if is_prime(NSPopInt()) then res = 1 end
	NSSetIntValue(ref, res)
end

まとめ

なんかすっきりしたけど、コメントのせいかファイルサイズ自体は増えてるんだよなあ。