欧拉筛求素数,果然非常快

Lua | 2018-03-23 16:54:12 | 阅读 1057 次 | 评论(0)

看到一个求素数的题目,忽然想试试欧拉筛有多快。

题目:求一千万内素数的个数。

先看最普通的筛子:1077秒

T = os.time()

--求iMaxN内的素数
local iMaxN = 10000000

--普通筛子
local iSS = {}	--素数数组
local iSZ = {}	--筛子
for i = 1, iMaxN do
	iSZ[i] = i
end

--过筛求出所有素数
for i = 2, math.sqrt(iMaxN) do
	for j = i + 1, iMaxN do
		if (j % i) == 0 then
			iSZ[j] = 0	--非素数置0
		end
	end
end

for i = 2, iMaxN do
	if iSZ[i] > 0 then
		iSS[#iSS + 1] = i	--放入素数数组
	end
end

print('用时:', os.time() - T)

print(#iSS)

os.execute('PAUSE')
再看欧拉筛:4秒!
--[[
1、从2至n枚举,对于元素i:
2、判断其是否已被筛除?否,则已经确定其为质数
3、枚举不大于i的最小质因子的质数
4、将i与这些质数的乘积筛除
5、返回2
--]]

T = os.time()

--求iMaxN内的素数
local iMaxN = 10000000	--再大就溢出了。。。。。。。

--欧拉法
local iSS = {}	--素数存放数组
local iSZ = {}	--筛子
for i = 1, iMaxN do
	iSZ[i] = i
end

for i = 2, iMaxN do
	if iSZ[i] > 0 then	--大于0说明未筛除,为素数
		iSS[#iSS + 1] = i	--放入素数数组
	end
	for j = 1, #iSS do	--枚举不大于i的最小质因子的质数
		local n = i * iSS[j]
		if n <= iMaxN then
			iSZ[n] = 0	--将i与这些质数的乘积筛除
		else
			break	--这句是关键
		end
	end
end

print('用时:', os.time() - T)

print(#iSS)

os.execute('PAUSE')

差了250倍!


文章评论,共0条
游客请输入验证码
浏览11236次