Sweet Snippet 系列之 埃拉托斯特尼(Eratosthenes)筛法
source link: https://blog.csdn.net/tkokof1/article/details/94657032
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Sweet Snippet 系列之 埃拉托斯特尼(Eratosthenes)筛法
埃拉托斯特尼(Eratosthenes)筛法的简单实现
遴选素数的埃拉托斯特尼(Eratosthenes)筛法想必大家都不陌生,不熟悉的朋友可以看看wiki,在此简单列出一份代码实现(Lua)
function Eratosthenes(n)
local is_prime = {}
-- init is_prime map
for i = 2, n do
is_prime[i] = true
end
-- eratosthenes filter
local beg_val = 2
local end_val = math.floor(math.sqrt(n))
for i = beg_val, end_val do
if is_prime[i] then
for j = i + i, n, i do
is_prime[j] = false
end
end
end
-- get primes
local primes = {}
for i = 2, n do
if is_prime[i] then
table.insert(primes, i)
end
end
return primes
end
简单测试一下:
print(#Eratosthenes(100)) // output 25
100 以内的素数是 25 个,有兴趣的朋友可以试试到底是哪 25 个~
Recommend
-
28
Sweet Snippet 之 BitMask
-
12
Sweet Snippet 之 Timeslice Update
-
24
Sweet Snippet 之 方差计算
-
14
Sweet Snippet 之 字符串编辑距离
-
14
Sweet Snippet 之 Gram-Schmidt 正交化
-
11
Sweet Snippet 之 Lua readonly table
-
13
Sweet Snippet 之 Lua Utils_tkokof1的专栏-CSDN博客 Sweet Snippet 之 Lua Utils ...
-
10
Sweet Snippet 系列之 扩展欧几里得算法
-
10
Sweet Snippet 系列之 有序列表
-
6
← 灾难期间的社会人口流动模型majer @ 2022.09.05 , 23:59...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK