赔率,即 2-互质数,由下式生成“滚轮子” [2]
,即从初始值 3 开始(类似地从 5、7、9、...)开始重复添加 2,
n=3; n+=2; n+=2; n+=2; ... # wheel = [2]
3 5 7 9
2-3-互质是通过重复添加 2、然后 4、再添加 2、然后 4 等生成的:
n=5; n+=2; n+=4; n+=2; n+=4; ... # wheel = [2,4]
5 7 11 13 17
这里我们确实需要知道从哪里开始添加 2 或 4 的差异,具体取决于初始值。对于 5、11、17...,它是 2(即轮盘的第 0 个元素);对于 7、13、19...,它是 4(即第 1 个元素)。
我们怎样才能知道从哪里开始呢?轮优化的要点是我们只处理这个互质序列(在本例中为 2-3-互质)。因此,在获得递归生成素数的代码部分中,我们还将维护滚轮流,并推进它,直到看到其中的下一个素数。轧制顺序需要产生two结果 - 值和车轮位置。因此,当我们看到质数时,我们也得到了相应的轮子位置,并且我们可以从轮子上的该位置开始生成其倍数。我们将所有内容乘以p
当然,要从p*p
:
for (i, p) # the (wheel position, summated value)
in enumerated roll of the wheel:
when p is the next prime:
multiples of p are m = p*p; # map (p*) (roll wheel-at-i from p)
m += p*wheel[i];
m += p*wheel[i+1]; ...
因此,字典中的每个条目都必须保持其当前值、其基素数和当前轮位置(在需要时,环绕到 0 以实现循环)。
为了产生结果素数,我们滚动另一个互素序列,并只保留其中不在字典中的元素,就像参考代码中一样。
update:经过几次迭代进行代码审查 https://codereview.stackexchange.com/q/92365/9064(非常感谢那里的贡献者!)为了提高速度,我尽可能多地使用 itertools 得到了这段代码:
from itertools import accumulate, chain, cycle, count
def wsieve(): # wheel-sieve, by Will Ness. ideone.com/mqO25A
wh11 = [ 2,4,2,4,6,2,6,4,2,4,6, 6,2,6,4,2,6,4,6,8,4,2, 4,
2,4,8,6,4,6,2,4,6,2,6, 6,4,2,4,6,2,6,4,2,4,2, 10,2,10]
cs = accumulate(chain([11], cycle(wh11))) # roll the wheel from 11
yield(next(cs)) # cf. ideone.com/WFv4f,
ps = wsieve() # codereview.stackexchange.com/q/92365/9064
p = next(ps) # 11
psq = p**2 # 121
D = dict(zip(accumulate(chain([0], wh11)), count(0))) # wheel roll lookup dict
mults = {}
for c in cs: # candidates, coprime with 210, from 11
if c in mults:
wheel = mults.pop(c)
elif c < psq:
yield c
continue
else: # c==psq: map (p*) (roll wh from p) = roll (wh*p) from (p*p)
i = D[(p-11) % 210] # look up wheel roll starting point
wheel = accumulate( chain( [psq],
cycle( [p*d for d in wh11[i:] + wh11[:i]])))
next(wheel)
p = next(ps)
psq = p**2
for m in wheel: # pop, save in m, and advance
if m not in mults:
break
mults[m] = wheel # mults[143] = wheel@187
def primes():
yield from (2, 3, 5, 7)
yield from wsieve()
与上面的描述不同,这段代码直接计算每个素数从哪里开始滚动,以生成它的倍数