Я изменяю неопределенное сито Эратосфена из здесь, чтобы оно использовало факторизацию колеса, чтобы пропустить больше составных частей, чем его текущая форма простой проверки всех шансы.
Я разработал, как сгенерировать шаги, которые нужно предпринять, чтобы добраться до всех промежутков вдоль колеса. После этого я решил, что могу просто заменить +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, я получаю правильную сумму 24133 для первых ста простых чисел, но когда я использую любой другой размер колеса, я получаю пропущенные простые числа, неправильные суммы и составные части. Даже колесо 2-3 (которое использует чередующиеся шаги 2 и 4) приводит к тому, что сито пропускает простые числа. Что я делаю неправильно?
