gpt4 book ai didi

ruby 1.8 素数succ算法

转载 作者:数据小太阳 更新时间:2023-10-29 07:30:35 27 4
gpt4 key购买 nike

我已经搜索了我能想到的每个站点,但无法确定 ruby​​ 1.8 用于在 mathn 下的 Prime 类中创建素数列表的基本算法。以下是 succ 方法的可运行版本,调用了 100 次(为了找到第 100 个素数)。有谁知道这是如何工作的?

number_of_primes = 100

seed = 1
primes = Array.new
counts = Array.new


while primes.size < number_of_primes
i = -1
size = primes.size
while i < size
if i == -1
seed += 1
i += 1
else
while seed > counts[i]
counts[i] += primes[i]
end
if seed != counts[i]
i += 1
else
i = -1
end
end
end
primes.push seed
counts.push (seed + seed)
end

puts seed

实际的代码当然是:http://ruby-doc.org/stdlib-1.8.7/libdoc/mathn/rdoc/Prime.html

它看起来不像筛选算法,因为没有要筛选的预定义列表,它也不是试验除法算法,因为没有除法或取模运算。我完全被难住了。

最佳答案

该算法基于埃拉托色尼筛法。

seed 是要测试素数的整数。 primes 是小于 seed 的素数列表,counts 包含大于 seed 的相应最小倍数。

counts 视为“下一个”划掉数字的列表,但每个素数只有一个,并且不断更新。当找到下一个最大的倍数时,如果我们恰好得到 seed,那么它不是素数,因此它会重置外循环(使用 i=-1)。

只有当我们更新了更大倍数的列表,而没有恰好遇到 seed 时,我们才能推断出 seed 是素数。

这里是稍微简化和注释的代码:

number_of_primes = 100

seed = 1
primes = []
counts = []

while primes.size < number_of_primes
seed += 1
i = 0
while i < primes.size # For each known prime
while seed > counts[i] # Update counts to hold the next multiple >= seed
counts[i] += primes[i] # by adding the current prime enough times
end
if seed != counts[i]
i += 1 # Go update next prime
else
i = 0 # seed is a multiple, so start over...
seed += 1 # with the next integer
end
end
# The current seed is not a multiple of any of the previously found primes, so...
primes.push seed
counts.push (seed + seed)
end

puts seed

关于ruby 1.8 素数succ算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13774680/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com