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

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

先看最普通的筛子：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')

--[[
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倍！