将轮分解加入无限筛

Question

我正在从这里修改Eratosthenes的无限筛子,所以它使用轮子分解来跳过更多的复合材料而不是当前检查所有可能性的形式.

我已经弄清楚如何生成步骤以达到车轮上的所有间隙.从那里我想我可以用+ 2代替这些轮子步骤,但它导致筛子跳过素数.这是代码:

from itertools import count, cycle

def dvprm(end):
    "finds primes by trial division. returns a list"
    primes=[2]
    for i in range(3, end+1, 2):
        if all(map(lambda x:i%x, primes)):
            primes.append(i)
    return primes

def prod(seq, factor=1):
    "sequence -> product"
    for i in seq:factor*=i
    return factor

def wheelGaps(primes):
    """returns list of steps to each wheel gap
    that start from the last value in primes"""
    strtPt= primes.pop(-1)#where the wheel starts
    whlCirm= prod(primes)# wheel's circumference

    #spokes are every number that are divisible by primes (composites)
    gaps=[]#locate where the non-spokes are (gaps)
    for i in xrange(strtPt, strtPt+whlCirm+1, 2):
        if not all(map(lambda x:i%x,primes)):continue#spoke 
        else: gaps.append(i)#non-spoke

    #find the steps needed to jump to each gap (beginning from the start of the wheel)
    steps=[]#last step returns to start of wheel
    for i,j in enumerate(gaps):
        if i==0:continue
        steps.append(j - gaps[i-1])
    return steps

def wheel_setup(num):
    "builds initial data for sieve"
    initPrms=dvprm(num)#initial primes from the "roughing" pump
    gaps = wheelGaps(initPrms[:])#get the gaps
    c= initPrms.pop(-1)#prime that starts the wheel

    return initPrms, gaps, c

def wheel_psieve(lvl=0, initData=None):
    '''postponed prime generator with wheels
    Refs:  http://stackoverflow.com/a/10733621
           http://stackoverflow.com/a/19391111'''

    whlSize=11#wheel size, 1 higher prime than
    # 5 gives 2- 3 wheel      11 gives 2- 7 wheel 
    # 7 gives 2- 5 wheel      13 gives 2-11 wheel
    #set to 0 for no wheel

    if lvl:#no need to rebuild the gaps, just pass them down the levels
        initPrms, gaps, c = initData
    else:#but if its the top level then build the gaps
        if whlSize>4:
            initPrms, gaps, c = wheel_setup(whlSize) 
        else:
            initPrms, gaps, c= dvprm(7), [2], 9

    #toss out the initial primes
    for p in initPrms:
        yield p

    cgaps=cycle(gaps)
    compost = {}#found composites to skip

    ps=wheel_psieve(lvl+1, (initPrms, gaps, c))

    p=next(ps)#advance lower level to appropriate square
    while p*p < c:
        p=next(ps)
    psq=p*p

    while True:
        step1 = next(cgaps)#step to next value

        step2=compost.pop(c, 0)#step to next multiple

        if not step2:

            #see references for details
            if c < psq:
                yield c
                c += step1
                continue

            else:
                step2=2*p
                p=next(ps)
                psq=p*p

        d = c + step2
        while d in compost:
            d+= step2
        compost[d]= step2

        c += step1

我用它来检查它:

def test(num=100):
    found=[]
    for i,p in enumerate(wheel_psieve(), 1):
        if i>num:break
        found.append(p)

    print sum(found)
    return found

当我将轮尺寸设置为0时,我得到前100个素数的正确总和为24133,但是当我使用任何其他轮尺寸时,我最终会丢失素数,不正确的总和和复合材料.即使是2-3轮(使用2和4的交替步骤)也会使筛子错过质量.我究竟做错了什么？

Answer 1

赔率,即2-coprimes,是通过"滚动轮子" 产生的[2],即通过重复添加2,从初始值3(类似于5,7,9 ,......)开始,

n=3; n+=2; n+=2; n+=2; ...           # wheel = [2]
  3     5     7     9

通过重复添加2,然后是4,再次增加2,然后是4,生成2-3个互质,依此类推:

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个互质)起作用.因此,在我们得到递归生成素数的代码部分中,我们还将保持滚动轮流,然后推进它直到我们看到其中的下一个素数.滚动序列需要产生两个结果 - 值和车轮位置.因此,当我们看到素数时,我们也得到相应的车轮位置,我们可以从车轮上的那个位置开始生成其倍数.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];    ...

因此,dict中的每个条目都必须保持其当前值,其基本素数和当前轮位(在需要时环绕为0以获得圆度).

为了产生最终的素数,我们滚动另一个互质序列,并且只保留那些不在dict中的元素,就像在参考代码中一样.

更新:在codereview上进行了几次迭代之后(非常感谢那里的贡献者!)我已经到了这个代码,尽可能使用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()

与上面的描述不同,此代码直接计算从每个素数开始滚动轮子的位置,以生成其倍数